Polynomial Time Algorithms for Finding Integer Relations among Real Numbers

DOI10.1137/0218059zbMath0692.10033OpenAlexW2027157239WikidataQ56959232 ScholiaQ56959232MaRDI QIDQ3033848

Jeffrey C. Lagarias, Bettina Just, Johan T. Håstad, 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 fractionapproximation algorithmscomputational number theoryinteger relationmultidimensional Euclidean algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Lattices and convex bodies (number-theoretic aspects) (11H06) Continued fractions and generalizations (11J70) Continued fraction calculations (number-theoretic aspects) (11Y65) Quadratic forms (reduction theory, extreme forms, etc.) (11H55)

Related Items

Complexity results for some eigenvector problems, Towards faster polynomial-time lattice reduction, Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Recovering Exact Results from Inexact Numerical Data in Algebraic Geometry, An improved lower bound for approximating shortest integer relation in \(\ell _{\infty }\) norm \((SIR_{\infty })\), Complex Dimensions of Self-Similar Fractal Strings and Diophantine Approximation, Real data-integer solution problems within the Blum-Shub-Smale computational model, Simultaneously good bases of a lattice and its reciprocal lattice, Cloud-Assisted LLL: A Secure and Efficient Outsourcing Algorithm for Approximate Shortest Vector Problem, Experimental Evaluation of Euler Sums, Inversion of Band-Limited Discrete Fourier Transforms of Binary Images: Uniqueness and Algorithms, Trilateration using unlabeled path or loop lengths, The PSLQ algorithm for empirical data, Thrackles: An Improved Upper Bound, Parallel integer relation detection: Techniques and applications, An optimal, stable continued fraction algorithm for arbitrary dimension, Distances from differences of roots of polynomials to the nearest integers, Improved low-density subset sum algorithms, Random Sampling Revisited: Lattice Enumeration with Discrete Pruning, A natural lattice basis problem with applications, Fast LLL-type lattice reduction, Selected Applications of LLL in Number Theory, A Numerical Transcendental Method in Algebraic Geometry: Computation of Picard Groups and Related Invariants, On the hardness of approximating shortest integer relations among rational numbers, Factoring polynomials over global fields, Challenges of symbolic computation: My favorite open problems. With an additional open problem by Robert M. Corless and David J. Jeffrey, Analysis of PSLQ, an integer relation finding algorithm, Simultaneous reduction of a lattice basis and its reciprocal basis