Polynomial time algorithms for finding integer reations among real numbers. (English) Zbl 0606.68033

Håstad, Johan; Helfrich, B.; Lagarias, J.; Schnorr, C. P.

Theoretical aspects of computer science, 3rd Annu. Symp., Orsay/France 1986, Lect. Notes Comput. Sci. 210, 105-118 (1986).

[For the entire collection see Zbl 0578.00004.]
We present algorithms, which when given a real vector \(x\in {\mathbb{R}}^ n\) and a parameter \(k\in {\mathbb{N}}\) as input either find an integer relation \(m\in {\mathbb{Z}}^ n\), \(m\neq 0\) with \(x^ Tm=0\) or prove there is no such integer relation with \(\| m\| \leq 2^ k\). One such algorithm halts after at most \(O(n^ 3(k+n))\) arithmetic operations using real numbers. It finds an integer relation that is no more than \(2^{(n-2)/2}\) times longer than the length of the shortest relation for x. Given a rational input \(x\in {\mathbb{Q}}^ n\) this algorithm halts in polynomially many bit operations. The basic algorithm of this kind is due to H. R. P. Ferguson and R. W. Forcade [Bull. Am. Math. Soc., New Ser. 1, 912- 914 (1979; Zbl 0424.10021)] and is closely related to the Lovász lattice basis reduction algorithm [A. K. Lenstra, H. W.Lenstra, and L. Lovász, Math. Ann. 261, 515-534 (1982; Zbl 0488.12001)].

MSC:

68Q25	Analysis of algorithms and problem complexity
11-04	Software, source code, etc. for problems pertaining to number theory
11H06	Lattices and convex bodies (number-theoretic aspects)
68W30	Symbolic computation and algebraic computation

Keywords:

computational number theory; lattice basis reduction algorithm

Citations:

Zbl 0578.00004; Zbl 0424.10021; Zbl 0488.12001