Lattice reduction

Short description: Mathematical operation

Lattice reduction in two dimensions: the black vectors are the given basis for the lattice (represented by blue dots), the red vectors are the reduced basis

In mathematics, the goal of lattice basis reduction is to find a basis with short, nearly orthogonal vectors when given an integer lattice basis as input. This is realized using different algorithms, whose running time is usually at least exponential in the dimension of the lattice.

Finding a reduced lattice basis is also closely related to the problem in crystallography of finding a unique unit cell. Historically reduction theory was first studied by Lagrange (1773) and independently by Gauss (1801), in order to classify binary quadratic forms, a classic problem in number theory. In a little sidenote to a book review in 1831, Gauss mentions that the reduction theory for certain quadratic forms is equivalent to finding a unit cell for point lattices and he sees the relevance for crystallography. This close relationship in number theory and geometry of point lattices inspired much of the successive work on quadratic forms culminating in Minkowski's important work "Geometry of Numbers" (1896 and 1910).

## Contents

* 1 Nearly orthogonal
* 2 In two dimensions
* 3 Applications
* 4 Algorithms
* 5 References

## Nearly orthogonal

One measure of nearly orthogonal is the orthogonality defect. This compares the product of the lengths of the basis vectors with the volume of the parallelepiped they define. For perfectly orthogonal basis vectors, these quantities would be the same.

Any particular basis of n vectors may be represented by a matrix B, whose columns are the basis vectors bi,i=1,…,n. In the fully dimensional case where the number of basis vectors is equal to the dimension of the space they occupy, this matrix is square, and the volume of the fundamental parallelepiped is simply the absolute value of the determinant of this matrix det⁡(B). If the number of vectors is less than the dimension of the underlying space, then volume is det⁡(BTB). For a given lattice Λ, this volume is the same (up to sign) for any basis, and hence is referred to as the determinant of the lattice det⁡(Λ) or lattice constant d(Λ).

The orthogonality defect is the product of the basis vector lengths divided by the parallelepiped volume;

δ(B)=Πi=1n‖bi‖det⁡(BTB)=Πi=1n‖bi‖d(Λ)

From the geometric definition it may be appreciated that δ(B)≥1 with equality if and only if the basis is orthogonal.

If the lattice reduction problem is defined as finding the basis with the smallest possible defect, then the problem is NP-complete.[1] However, there exist polynomial time algorithms to find a basis with defect δ(B)≤c where c is some constant depending only on the number of basis vectors and the dimension of the underlying space (if different) . This is a good enough solution in many practical applications{{Citation needed|date=July 2022}

## In two dimensions

For a basis consisting of just two vectors, there is a simple and efficient method of reduction closely analogous to the Euclidean algorithm for the greatest common divisor of two integers. As with the Euclidean algorithm, the method is iterative; at each step the larger of the two vectors is reduced by adding or subtracting an integer multiple of the smaller vector.

The pseudocode of the algorithm, often known as Lagrange's algorithm or the Lagrange-Gauss algorithm, is as follows:

Input: (u,v) a basis for the lattice L. Assume that ||v||≤||u||, otherwise swap them.
Output: A basis (u,v) with ||u||=λ1(L),||v||=λ2(L).

While ||v||<||u||:
q:=⌊⟨u,v||v||2⟩⌉ # Round to nearest integer
r:=u−qv
u:=v
v:=r

See the section on Lagrange's algorithm in [2] for further details.

## Applications

Lattice reduction algorithms are used in a number of modern number theoretical applications, including in the discovery of a spigot algorithm for π. Although determining the shortest basis is possibly an NP-complete problem, algorithms such as the LLL algorithm[3] can find a short (not necessarily shortest) basis in polynomial time with guaranteed worst-case performance. LLL is widely used in the cryptanalysis of public key cryptosystems.

When used to find integer relations, a typical input to the algorithm consists of an augmented n×n identity matrix with the entries in the last column consisting of the n elements (multiplied by a large positive constant w to penalize vectors that do not sum to zero) between which the relation is sought.

The LLL algorithm for computing a nearly-orthogonal basis was used to show that integer programming in any fixed dimension can be done in polynomial time.[4]

## Algorithms

The following algorithms reduce lattice bases; several public implementations of these algorithms are also listed.

Year  | Algorithm  | Implementation

|
|

1773  | Lagrange reduction for binary quadratic forms  |
1801  | Gauss reduction for binary quadratic forms in his early work Disquisitiones Arithmeticae  |
1831  | Gauss mentions in a book review the relationship of certain quadratic forms with 2D and 3D point lattices as a side note (Goettingische gelehrte Anzeigen 1831, section 108)  |
1840  | Gauss' book review is reprinted in Crelle's Journal  |
1850  | Hermite laying the groundwork for lattice reduction in higher dimensions  |
1851  | Eisenstein's paper laying the groundwork for Niggli's theory  |
1873  | Korkine and Zolotareff refine Hermite's method (HKZ)  |
1874  | Selling reduction for ternary quadratic forms using geometric concepts by Gauss  |
1896  | Minkowski reduction by shortest successive vectors (up to 4D)  |
1928  | Niggli's reduction for 3D lattices in crystallography to define a best unit cell  |
1933  | Delaunay (Delone) reduction optimizing Selling's method for crystallography  |
1970  | Santoro and Mighell propose a method to find the reduced unit cell in crystallography  |
1982  | Lenstra–Lenstra–Lovász reduction  | NTL, fplll
1987  | Block Korkine–Zolotarev[5] | NTL, fplll
1993  | Seysen Reduction[6] |

## References

1. ↑ Yap, Chee Keng (2000). "9: Lattice Reduction and Applications". Fundamental Problems of Algorithmic Algebra. New York, Oxford: Oxford University Press. pp. 238. ISBN 0-19-512516-9.
2. ↑ Nguyen, Phong Q. (2009). "Hermite’s Constant and Lattice Algorithms". The LLL Algorithm. Information Security and Cryptography. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 19–69. doi:10.1007/978-3-642-02295-1_2. ISBN 978-3-642-02294-4.
3. ↑ Lenstra, A. K.; Lenstra, H. W. Jr.; Lovász, L. (1982). "Factoring polynomials with rational coefficients". Mathematische Annalen 261 (4): 515–534. doi:10.1007/BF01457454.
4. ↑ "Integer programming with a fixed number of variables". Mathematics of Operations Research 8 (4): 538–548. 1983. doi:10.1287/moor.8.4.538.
5. ↑ Hanrot, Guillaume; Stehlé, Damien (2008). "Worst-Case Hermite-Korkine-Zolotarev Reduced Lattice Bases". arXiv:0801.3331 [math.NT].
6. ↑ Seysen, Martin (September 1993). "Simultaneous reduction of a lattice basis and its reciprocal basis". Combinatorica 13 (3): 363–376. doi:10.1007/BF01202355.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Lattice reduction. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Lattice_reduction&oldid=4296832"