Polynomial Time Algorithms for Finding Integer Relations among Real Numbers

DOI10.1137/0218059zbMath0692.10033WikidataQ56959232 ScholiaQ56959232MaRDI QIDQ3033848

Jeffrey C. Lagarias, Johan T. Håstad, Bettina Just, Claus Peter Schnorr

Publication date: 1989

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0218059

zbMATH Keywords

continued fraction; approximation algorithms; computational number theory; integer relation; multidimensional Euclidean algorithm

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

11Y16: Number-theoretic algorithms; complexity

11H06: Lattices and convex bodies (number-theoretic aspects)

11J70: Continued fractions and generalizations

11Y65: Continued fraction calculations (number-theoretic aspects)

11H55: Quadratic forms (reduction theory, extreme forms, etc.)

Related Items

Experimental Evaluation of Euler Sums, A natural lattice basis problem with applications, Complexity results for some eigenvector problems, Complex Dimensions of Self-Similar Fractal Strings and Diophantine Approximation, Selected Applications of LLL in Number Theory, An improved lower bound for approximating shortest integer relation in \(\ell _{\infty }\) norm \((SIR_{\infty })\), Factoring polynomials over global fields, Simultaneously good bases of a lattice and its reciprocal lattice, Distances from differences of roots of polynomials to the nearest integers, Improved low-density subset sum algorithms, On the hardness of approximating shortest integer relations among rational numbers, Simultaneous reduction of a lattice basis and its reciprocal basis, Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Real data-integer solution problems within the Blum-Shub-Smale computational model, Challenges of symbolic computation: My favorite open problems. With an additional open problem by Robert M. Corless and David J. Jeffrey, Fast LLL-type lattice reduction, Parallel integer relation detection: Techniques and applications, Analysis of PSLQ, an integer relation finding algorithm