zbMATH — the first resource for mathematics

A more efficient algorithm for lattice basis reduction. (English) Zbl 0595.68038
Automata, languages and programming, Proc. 13th Int. Colloq., Rennes/France 1986, Lect. Notes Comput. Sci. 226, 359-369 (1986).
Summary: [For the entire collection see Zbl 0587.00019.]
The famous lattice basis reduction algorithm of L. Lovász transforms a given integer lattice basis \(b_ 1,\dots,b_ n\in {\mathbb Z}^ n\) into a reduced basis, and does this by \(O(n^ 4 \log B)\) arithmetic operations on \(O(n \log B)\)-bit integers. Here \(B\) bounds the Euclidean length of the input vectors, i.e. \(\| b_ 1\|^ 2,\dots,\| b_ n\|^ 2\leq B\). The new algorithm operates on integers with at most \(O(n+\log B)\) bits and uses at most \(O(n^ 4 \log B)\) arithmetic operations on such integers. This reduces the number of bit operations for reduction by a factor \(n^ 2\) if \(n\) is proportional to \(\log B\) and if standard arithmetic is used. For most practical cases reduction can be done without very large integer arithmetic but with floating point arithmetic instead.

68Q25 Analysis of algorithms and problem complexity
11Y16 Number-theoretic algorithms; complexity
68W30 Symbolic computation and algebraic computation
90C10 Integer programming