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
      [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
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references