# 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.

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