Lattice reduction (Q4238958)

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 1276813
Language Label Description Also known as
default for all languages
No label defined
    English
    Lattice reduction
    scientific article; zbMATH DE number 1276813

      Statements

      0 references
      20 April 1999
      0 references
      LLL lattice reduction
      0 references
      reduction in higher dimensions
      0 references
      implementation
      0 references
      Lattice reduction (English)
      0 references
      The chapter contains a brief review of the elements of LLL lattice reduction. Section 2 introduces the relevant background material, recalling the characterization of lattices of \({\mathbb R}^n\) as discrete additive subgroups for which there exists \({\mathbb R}\)-linearly independent bases. The discriminant is defined, Minkowski's theorem recalled and the shortest lattice vector problem stated. The particular case of lattice reduction in two dimensions is examined in section 3 giving an upper bound of \((4/3)^{1/4} d(L)^{1/2}\) for the length of the shortest vector, where \(d(L)\) is the lattice discriminant. The case of reduction in higher dimensions is considered in the following section, where the basic theorem on the properties of LLL reduction is stated and proved. Section 5 introduces certain aspects for consideration in the implementation of the LLL algorithm. The last section discusses an application of the algorithm to the problem of finding \({\mathbb Z}\)-linear combinations of a given set of real numbers with small values. For the entire collection see Zbl 0924.13021.
      0 references

      Identifiers