No label defined (Q3739233)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3972987
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3972987 |
Statements
1986
0 references
computational number theory
0 references
basis reduction algorithm
0 references
shortest vector
0 references
lattice
0 references
0.8811445832252502
0 references
0.8805056810379028
0 references
0.8754620552062988
0 references
[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.
0 references