- Lattice reduction
In mathematics, the goal of lattice basis reduction is given an integer lattice basis as input, to find a basis with short, nearly
orthogonal vectors. This is realized using different algorithms, whose running time is usually at least exponential in the dimension of the lattice.Applications
Lattice reduction algorithms are used in a number of modern number theoretical applications, including in the discovery of a spigot algorithm for pi. Although determining the shortest basis is possibly an NP-complete problem, algorithms such as the LLL algorithm can find a short basis in polynomial time with guaranteed worst-case performance. LLL is widely used in the
cryptanalysis ofpublic key cryptosystems.When used to find integer relations, a typical input to the algorithm consists of an augmented nxn 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.
Algorithms
The following algorithms reduce lattice bases. They can be compared in terms of runtime and approximation to an optimal solution, always relative to the dimension of the given lattice. If there are public implementations of these algorithms this should also be noted here.
References
*cite book
last = Yap
first = Chee-Keng
title = Fundamental Problems of Algorithmic Algebra
url = http://www.cs.nyu.edu/yap/book/berlin/
accessdate = 2008-08-25
year = 2000
publisher = Oxford University Press
location = Oxford, New York
isbn = 0-19-512516-9
pages = pp. 219-257
chapter = Chap. 8 Gaussian Lattice Reduction - Chap. 9 Lattice Reduction and Applications
Wikimedia Foundation. 2010.
