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(d⁵nlog³B).

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)