Lenstra–Lenstra–Lovász lattice basis reduction algorithm

The Lenstra–Lenstra–Lovász lattice basis reduction (LLL) is a polynomial time lattice reduction algorithm. 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 (short, nearly orthogonal) lattice basis in time

$O(d^{5}n\log ^{3}B)\,$.

The original applications were to give polynomial time algorithms for factorizing polynomials with rational coefficients into irreducible polynomials, and for solving the integer linear programming problem in fixed dimensions.

Output quality

The LLL algorithm computes so-called LLL-reduced bases. Informally, a reduced basis is one in which the first vector is the shortest vector in the lattice, the second basis vector is the shortest vector linearly independent of the first, and so on. Unfortunately there is no known algorithm to compute such a basis except for lattices of dimensions 1, 2, or 3. What is known to be computable is a basis which is nearly reduced, in the sense that that there are absolute bounds $c_{i}>1$ such that the first basis vector is no more than $c_{1}$ times as long as the shortest vector in the lattice, the second basis vector is likewise within $c_{2}$ of the shortest vector independent of that, and so on. This "global" description of an LLL-reduced basis is proved as a consequence of a "local" description, which is easily checked for a given set of vectors. (The description below may be interpreted to say that each vector is "nearly orthogonal" to its predecessors, and "not too much shorter" than them.)

The precise definition of LLL-reduced is as follows: the basis

$\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{N}\}$,

with its Gram–Schmidt process orthogonal basis,

$\mathbf {B} '=\{\mathbf {b} '_{1},\mathbf {b} '_{2},\dots ,\mathbf {b} '_{N}\}$

is LLL-reduced if there exists a parameter p in (0.25,1] such that

1. $\forall i\leq N,j<i\colon \left|\mu _{i,j}\right|\leq 0.5,$
2. $\forall i<N\colon p\Vert \mathbf {b} '_{i}\Vert ^{2}\leq \left\Vert \mu _{i+1,i}\mathbf {b} '_{i}+\mathbf {b} '_{i+1}\right\Vert ^{2},$

where

$\mu _{i,j}={\frac {\langle \mathbf {b} _{i},\mathbf {b} '_{j}\rangle }{\langle \mathbf {b} '_{j},\mathbf {b} '_{j}\rangle }}$, for any i>j.

Note that although LLL-reduction is well-defined for p=1, the polynomial-time complexity is guaranteed only for p in (0.25,1).

Applications

The LLL algorithm has found numerous other applications in MIMO detection algorithms and cryptanalysis of public-key encryption schemes: knapsack cryptosystems, RSA with particular settings, NTRUEncrypt, and so forth. The algorithm can be used to find integer solutions to many problems not immediately phrased as requiring lattice reduction. For example, if it is believed that r=1.618034 is a (slightly rounded) root to a quadratic equation with integer coefficients, one may apply the LLL reduction to the lattice in $R^{4}$ spanned by $[1,0,0,10000r^{2}],[0,1,0,10000r],$ and $[0,0,1,10000]$. The first vector in the reduced basis will be an integer linear combination of these three, thus necessarily of the form $[a,b,c,10000(ar^{2}+br+c)]$; but such a vector is "short" only if a,b,c are small and $ar^{2}+br+c$ is very small. Thus the first three entries of this short vector are likely to be the coefficients of the integral quadratic polynomial which has r as a root. (In this application the LLL algorithm finds the shortest vector to be [1, -1, -1, 0.00025] and indeed $x^{2}-x-1$ has a root equal to 1.6180339887...)

Implementations

LLL is implemented in

• Arageli as the function lll_reduction_int
• fpLLL as a stand-alone implementation
• GAP as the function LLLReducedBasis
• LiDIA LT package as the function/method lll
• Macaulay2 as the function LLL. (One must load the package LLLBases)
• Magma as the functions LLL and LLLGram (taking a gram matrix)
• Maple as the function IntegerRelations[LLL]
• Mathematica as the function LatticeReduce
• PARI/GP as the function qflll
• SAGE as the method LLL driven by fpLLL and NTL
• Victor Shoup's Number Theory Library (NTL) as the function LLL

References

• 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. MR0682664.{{cite journal}}: CS1 maint: multiple names: authors list (link)

• Peter Borwein's Computational Excursions in Analysis and Number Theory (ISBN 0-387-95444-9) contains a full description of the algorithm along with a pseudo-code implementation.