Schnorr, C. P. 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. Cited in 1 ReviewCited in 2 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 11Y16 Number-theoretic algorithms; complexity 68W30 Symbolic computation and algebraic computation 90C10 Integer programming Keywords:integer lattice basis; integer arithmetic; floating point arithmetic Citations:Zbl 0587.00019 PDFBibTeX XML