Lenstra–Lenstra–Lovász lattice basis reduction algorithm

LLL reduction

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

B = { b 0 , b 1 , … , b n } ,

define its Gram–Schmidt process orthogonal basis

B ∗ = { b 0 ∗ , b 1 ∗ , … , b n ∗ } ,

and the Gram-Schmidt coefficients

μ i , j = ⟨ b i , b j ∗ ⟩ ⟨ b j ∗ , b j ∗ ⟩ , for any 1 ≤ j < i ≤ n .

Then the basis B is LLL-reduced if there exists a parameter δ in (0.25,1] such that the following holds:

1. (size-reduced) For 1 ≤ j < i ≤ n : | μ i , j | ≤ 0.5 . By definition, this property guarantees the length reduction of the ordered basis.
2. (Lovász condition) For k = 1,2,..,n : δ ∥ b k − 1 ∗ ∥ 2 ≤ ∥ b k ∗ ∥ 2 + μ k , k − 1 2 ∥ b k − 1 ∗ ∥ 2 .

Here, estimating the value of the δ parameter, we can conclude how well the basis is reduced. Greater values of δ lead to stronger reductions of the basis. Initially, A. Lenstra, H. Lenstra and L. Lovász demonstrated the LLL-reduction algorithm for δ = 3 4 . Note that although LLL-reduction is well-defined for δ = 1 , the polynomial-time complexity is guaranteed only for δ in (0.25,1).

The LLL algorithm computes LLL-reduced bases. There is no known efficient algorithm to compute a basis in which the basis vectors are as short as possible for lattices of dimensions greater than 4. However, an LLL-reduced basis is nearly as short as possible, in the sense that there are absolute bounds c i > 1 such that the first basis vector is no more than c 1 times as long as a shortest vector in the lattice, the second basis vector is likewise within c 2 of the second successive minimum, and so on.

LLL Algorithm

The following description is based on (Hoffstein, Pipher & Silverman 2008, Theorem 6.68), with the corrections from the errata

INPUT:

▹ a lattice basis b 0 , b 1 , … , b n ∈ Z m , ▹ parameter δ with 1 4 < δ < 1 , most commonly δ = 3 4

PROCEDURE:

Perform Gram-Schmidt, but do not normalize: o r t h o := g r a m S c h m i d t ( { b 0 , … , b n } ) = { b 0 ∗ , … , b n ∗ } Define μ i , j := ⟨ b i , b j ∗ ⟩ ⟨ b j ∗ , b j ∗ ⟩ , which must always use the most current values of b i , b j ∗ . Let k = 1 while k ≤ n do for j from k − 1 to 0 do if | μ k , j | > 1 2 do b k = b k − ⌊ μ k , j ⌉ b j Update ortho entries and related μ i , j 's as needed. (The naive method is to recompute o r t h o := g r a m S c h m i d t ( { b 0 , … , b n } ) = { b 0 ∗ , … , b n ∗ } whenever a b i changes.) end if end for if ⟨ b k ∗ , b k ∗ ⟩ ≥ ( δ − ( μ k , k − 1 ) 2 ) ⟨ b k − 1 ∗ , b k − 1 ∗ ⟩ then k = k + 1 else Swap b k and b k − 1 . Update ortho entries and related μ i , j 's as needed. (See above comment.) k = max ( k − 1 , 1 ) end if end while

OUTPUT: LLL reduced basis b 0 , b 1 , … , b n

Example

The following presents an example due to W. Bosma.

Let a lattice basis b 1 , b 2 , b 3 ∈ Z 3 , be given by the columns of

[ 1 − 1 3 1 0 5 1 2 6 ]

Then according to the LLL algorithm we obtain the following:

Apply a SWAP, continue algorithm with the lattice basis, which is given by columns

[ 1 4 − 1 1 5 0 1 4 2 ]

Implement the algorithm steps again.

LLL reduced basis

[ 0 1 − 1 1 0 0 0 1 2 ]

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.

In particular, the LLL algorithm forms a core of one of the integer relation algorithms. For example, if it is believed that r=1.618034 is a (slightly rounded) root to an unknown quadratic equation with integer coefficients, one may apply LLL reduction to the lattice in R 4 spanned by [ 1 , 0 , 0 , 10000 r 2 ] , [ 0 , 1 , 0 , 10000 r ] , 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 ( a r 2 + b r + c ) ] ; but such a vector is "short" only if a, b, c are small and a r 2 + b r + c is even smaller. 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 example 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 the golden ratio, 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

Macaulay2 as the function LLL in 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

Number Theory Library (NTL) as the function LLL

PARI/GP as the function qflll

Pymatgen as the function analysis.get_lll_reduced_lattice

SageMath as the method LLL driven by fpLLL and NTL