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
20 April 1999
0 references
LLL lattice reduction
0 references
reduction in higher dimensions
0 references
implementation
0 references
0.8675451278686523
0 references
0.8389403223991394
0 references
0.8364881277084351
0 references
0.8330671787261963
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