Lattice reduction

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 of public 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.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Lattice based cryptography — is the generic term for asymmetric cryptographic primitives based on lattice. HistoryLattice have first been discovered by mathematicans Lagrange and Gauss. Lattice have been used laterly in computer algorithms and in cryptanalysis. In 1996 Atjai …   Wikipedia

  • Reduction — Reduction, reduced, or reduce may refer to:cienceChemistry*Reduction – chemical reaction in which atoms have their oxidation number (oxidation state) changed. **Reduced gas – a gas with a low oxidation number **Ore reduction: see… …   Wikipedia

  • Lattice problem — In computer science, lattice problems are a class of optimization problems on lattices. The conjectured intractability of such problems is central to construction of secure lattice based cryptosystems. For applications in such cryptosystems,… …   Wikipedia

  • Lattice (group) — A lattice in the Euclidean plane. In mathematics, especially in geometry and group theory, a lattice in Rn is a discrete subgroup of Rn which spans the real vector space Rn. Every lattice in Rn …   Wikipedia

  • Lenstra–Lenstra–Lovász lattice basis reduction algorithm — The Lenstra–Lenstra–Lovász lattice basis reduction (LLL) is a polynomial time lattice reduction algorithm invented by Arjen Lenstra, Hendrik Lenstra and László Lovász. Given as input d lattice basis vectors with n dimensional integer coordinates… …   Wikipedia

  • International Workshops on Lattice QCD and Numerical Analysis — The International Workshops on Lattice QCD and Numerical Analysis first started in 1995. The aim is to bring together applied mathematicians and theoretical physicists as well as to stimulate the exchange of ideas between leading experts in the… …   Wikipedia

  • Turing reduction — In computability theory, a Turing reduction from a problem A to a problem B, named after Alan Turing, is a reduction which solves A, assuming B is already known (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to …   Wikipedia

  • NTRUEncrypt — The NTRUEncrypt public key cryptosystem, also known as the NTRU encryption algorithm, is a lattice based alternative to RSA and ECC and is based on the shortest vector problem in a lattice (i.e. is not breakable using quantum computers).… …   Wikipedia

  • List of mathematics articles (L) — NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… …   Wikipedia

  • Coppersmith method — The Coppersmith method, proposed by Don Coppersmith, is a method to find small integer roots of polynomial equations. These polynomials can be univariate or bivariate. In cryptography the algorithm is mainly used in attacks on RSA when parts of… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”