scientific article; zbMATH DE number 3972987

From MaRDI portal
Publication:3739233





[For the entire collection see Zbl 0592.00028.] This expository paper describes the basis reduction algorithm of \textit{A. K. Lenstra}, \textit{H. W. Lenstra} jun. and \textit{L. Lovász} [Math. Ann. 261, 515--534 (1982; Zbl 0488.12001)] and its application to the problem of finding a shortest nonzero vector in a lattice. After reviewing the basic facts about lattices, the classical algorithm for finding the shortest nonzero vector in a two-dimensional lattice is explained. The general algorithm is given in terms of the two-dimensional one. Its direct application yields a \(O(\exp (n^ 3))\) algorithm for the computation of a shortest vector in an \(n\)-dimensional lattice. An improvement of this algorithm due to the author has complexity \(n^{o(n)}\). Finally, various applications and open problems are mentioned.




Cited in
(42)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3739233)