Science Fair Project Encyclopedia
Lenstra-Lenstra-Lovász lattice reduction algorithm
The Lenstra-Lenstra-Lovász lattice reduction algorithm, given as input a lattice basis, outputs a basis with short, nearly orthogonal vectors. More precisely, given as input d lattice basis vectors with n-dimensional integer coordinates and a norm lesser than B, the LLL algorithm outputs an LLL-reduced lattice basis in time O(d5nlog3B).
The LLL algorithm has found numerous applications in cryptanalysis of public-key encryption schemes: knapsack cryptosystems, RSA with particular settings...
Reference:
A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovász, Factoring Polynomials with Rational Coefficients, Math. Ann. 261 (1982)
Last updated: 06-05-2005 01:41:36
10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details