Lattice reduction
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.
- Reduction formulae for Euclidean lattice theories
- Matrices and the LLL algorithm
- Lattice basis reduction. An introduction to the LLL algorithm and its applications
- Lattice Reduction for Modular Knapsack
- Reductions of integrable lattices
- The Generalized Basis Reduction Algorithm
- Flags and lattice basis reduction
- A generalization of LLL lattice basis reduction over imaginary quadratic fields
- Lattice refinement strategies
This page was built for publication: Lattice reduction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4238958)
