×

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.

MSC:

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

Citations:

Zbl 0587.00019