# Lenstra–Lenstra–Lovász lattice basis reduction algorithm

The Lenstra–Lenstra–Lovász (LLL) lattice basis reduction algorithm is a polynomial time lattice reduction algorithm invented by Arjen Lenstra, Hendrik Lenstra and László Lovász in 1982.[1] Given a basis ${\displaystyle \mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}}$ with n-dimensional integer coordinates, for a lattice L (a discrete subgroup of Rn) with ${\displaystyle \ d\leq n}$, the LLL algorithm calculates an LLL-reduced (short, nearly orthogonal) lattice basis in time

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

where B is the largest length of ${\displaystyle b_{i}}$ under the Euclidean norm.

The original applications were to give polynomial-time algorithms for factorizing polynomials with rational coefficients, for finding simultaneous rational approximations to real numbers, and for solving the integer linear programming problem in fixed dimensions.

## LLL reduction

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

${\displaystyle \mathbf {B} =\{\mathbf {b} _{0},\mathbf {b} _{1},\dots ,\mathbf {b} _{n}\},}$

define its Gram–Schmidt process orthogonal basis

${\displaystyle \mathbf {B} ^{*}=\{\mathbf {b} _{0}^{*},\mathbf {b} _{1}^{*},\dots ,\mathbf {b} _{n}^{*}\},}$

and the Gram-Schmidt coefficients

${\displaystyle \mu _{i,j}={\frac {\langle \mathbf {b} _{i},\mathbf {b} _{j}^{*}\rangle }{\langle \mathbf {b} _{j}^{*},\mathbf {b} _{j}^{*}\rangle }}}$, for any ${\displaystyle 1\leq j.

Then the basis ${\displaystyle B}$ is LLL-reduced if there exists a parameter ${\displaystyle \delta }$ in (0.25,1] such that the following holds:

1. (size-reduced) For ${\displaystyle 1\leq j. By definition, this property guarantees the length reduction of the ordered basis.
2. (Lovász condition) For k = 1,2,..,n ${\displaystyle \colon \delta \Vert \mathbf {b} _{k-1}^{*}\Vert ^{2}\leq \Vert \mathbf {b} _{k}^{*}\Vert ^{2}+\mu _{k,k-1}^{2}\Vert \mathbf {b} _{k-1}^{*}\Vert ^{2}}$.

Here, estimating the value of the ${\displaystyle \delta }$ parameter, we can conclude how well the basis is reduced. Greater values of ${\displaystyle \delta }$ lead to stronger reductions of the basis. Initially, A. Lenstra, H. Lenstra and L. Lovász demonstrated the LLL-reduction algorithm for ${\displaystyle \delta ={\frac {3}{4}}}$. Note that although LLL-reduction is well-defined for ${\displaystyle \delta =1}$, the polynomial-time complexity is guaranteed only for ${\displaystyle \delta }$ 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.[citation needed] However, an LLL-reduced basis is nearly as short as possible, in the sense that there are absolute bounds ${\displaystyle c_{i}>1}$ such that the first basis vector is no more than ${\displaystyle c_{1}}$ times as long as a shortest vector in the lattice, the second basis vector is likewise within ${\displaystyle 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 [2]

INPUT:

${\displaystyle \triangleright }$ a lattice basis ${\displaystyle b_{0},b_{1},\dots ,b_{n}\in Z^{m}}$,
${\displaystyle \triangleright }$ parameter ${\displaystyle \delta }$ with ${\displaystyle {\frac {1}{4}}<\delta <1}$, most commonly ${\displaystyle \delta ={\frac {3}{4}}}$

PROCEDURE:

   Perform Gram-Schmidt, but do not normalize:
${\displaystyle ortho:=\mathrm {gramSchmidt} (\{b_{0},\dots ,b_{n}\})=\{b_{0}^{*},\dots ,b_{n}^{*}\}}$
Define ${\displaystyle \scriptstyle \mu _{i,j}:={\frac {\langle b_{i},b_{j}^{*}\rangle }{\langle b_{j}^{*},b_{j}^{*}\rangle }}}$, which must always use the most current values of ${\displaystyle \scriptstyle b_{i},b_{j}^{*}}$.
Let ${\displaystyle k=1}$
while ${\displaystyle k\leq n}$ do
for j  from ${\displaystyle k-1}$ to 0 do
if ${\displaystyle |\mu _{k,j}|>{\frac {1}{2}}}$ do
${\displaystyle b_{k}=b_{k}-\lfloor \mu _{k,j}\rceil b_{j}}$
Update ortho entries and related ${\displaystyle \scriptstyle \mu _{i,j}}$'s as needed.
(The naive method is to recompute ${\displaystyle \scriptstyle ortho:=\mathrm {gramSchmidt} (\{b_{0},\dots ,b_{n}\})=\{b_{0}^{*},\dots ,b_{n}^{*}\}}$ whenever a ${\displaystyle \scriptstyle b_{i}}$ changes.)
end if
end for
if ${\displaystyle \langle b_{k}^{*},b_{k}^{*}\rangle \geq (\delta -(\mu _{k,k-1})^{2})\langle b_{k-1}^{*},b_{k-1}^{*}\rangle }$ then
${\displaystyle k=k+1}$
else
Swap ${\displaystyle \scriptstyle b_{k}}$ and ${\displaystyle \scriptstyle b_{k-1}}$.
Update ortho entries and related ${\displaystyle \scriptstyle \mu _{i,j}}$'s as needed. (See above comment.)
${\displaystyle k=\max(k-1,1)}$
end if
end while


OUTPUT: LLL reduced basis ${\displaystyle b_{0},b_{1},\dots ,b_{n}}$

## Example

The following presents an example due to W. Bosma.[3]

INPUT:

Let a lattice basis ${\displaystyle \mathbf {b} _{1},\mathbf {b} _{2},\mathbf {b} _{3}\in Z^{3}}$, be given by the columns of

${\displaystyle {\begin{bmatrix}1&-1&3\\1&0&5\\1&2&6\end{bmatrix}}}$

Then according to the LLL algorithm we obtain the following:

1. ${\displaystyle b_{1}^{*}=b_{1}={\begin{bmatrix}1\\1\\1\end{bmatrix}},B_{1}=\langle b_{1}^{*},b_{1}^{*}\rangle ={\begin{bmatrix}1\\1\\1\end{bmatrix}}{\begin{bmatrix}1\\1\\1\end{bmatrix}}=3}$
2. For ${\displaystyle i=2}$ DO:
1. For ${\displaystyle j=1}$ set ${\displaystyle \mu _{2,1}={\frac {\langle b_{2},b_{1}^{*}\rangle }{B_{1}}}={\frac {{\begin{bmatrix}-1\\0\\2\end{bmatrix}}{\begin{bmatrix}1\\1\\1\end{bmatrix}}}{3}}={\frac {1}{3}}\left(<{\frac {1}{2}}\right)}$ and ${\displaystyle b_{2}^{*}=b_{2}-\mu _{2,1}b_{1}^{*}={\begin{bmatrix}-1\\0\\2\end{bmatrix}}-{\frac {1}{3}}{\begin{bmatrix}1\\1\\1\end{bmatrix}}={\begin{bmatrix}{\frac {-4}{3}}\\{\frac {-1}{3}}\\{\frac {5}{3}}\end{bmatrix}}.}$
2. ${\displaystyle B_{2}=\langle b_{2}^{*},b_{2}^{*}\rangle ={\begin{bmatrix}{\frac {-4}{3}}\\{\frac {-1}{3}}\\{\frac {5}{3}}\end{bmatrix}}{\begin{bmatrix}{\frac {-4}{3}}\\{\frac {-1}{3}}\\{\frac {5}{3}}\end{bmatrix}}={\frac {14}{3}}.}$
3. ${\displaystyle \mathbf {k} :=2}$
4. Here the step 4 of the LLL algorithm is skipped as size-reduced property holds for ${\displaystyle \mu _{2,1}}$
5. For ${\displaystyle i=3}$ and for ${\displaystyle j=1,2}$ calculate ${\displaystyle \mu _{i,j}}$ and ${\displaystyle B_{i}}$:

${\displaystyle \mu _{3,1}={\frac {\langle b_{3},b_{1}^{*}\rangle }{B_{1}}}={\frac {{\begin{bmatrix}3\\5\\6\end{bmatrix}}{\begin{bmatrix}1\\1\\1\end{bmatrix}}}{3}}={\frac {14}{3}}(>{\frac {1}{2}})}$

hence ${\displaystyle b_{3}^{*}=b_{3}-\mu _{3,1}b_{1}^{*}={\begin{bmatrix}3\\5\\6\end{bmatrix}}-{\frac {14}{3}}{\begin{bmatrix}1\\1\\1\end{bmatrix}}={\begin{bmatrix}{\frac {-5}{3}}\\{\frac {1}{3}}\\{\frac {4}{3}}\end{bmatrix}}}$

and ${\displaystyle \mu _{3,2}={\frac {\langle b_{3},b_{2}^{*}\rangle }{B_{2}}}={\frac {{\begin{bmatrix}3\\5\\6\end{bmatrix}}{\begin{bmatrix}{\frac {-4}{3}}\\{\frac {-1}{3}}\\{\frac {5}{3}}\end{bmatrix}}}{\frac {14}{3}}}={\frac {13}{14}}\left(>{\frac {1}{2}}\right)}$

hence ${\displaystyle b_{3}^{*}=b_{3}^{*}-\mu _{3,2}b_{2}^{*}={\begin{bmatrix}{\frac {-5}{3}}\\{\frac {1}{3}}\\{\frac {4}{3}}\end{bmatrix}}-{\frac {13}{14}}{\begin{bmatrix}{\frac {-4}{3}}\\{\frac {-1}{3}}\\{\frac {5}{3}}\end{bmatrix}}={\begin{bmatrix}{\frac {-18}{42}}\\{\frac {27}{42}}\\{\frac {-9}{42}}\end{bmatrix}}={\begin{bmatrix}{\frac {-6}{14}}\\{\frac {9}{14}}\\{\frac {-3}{14}}\end{bmatrix}}}$ and

${\displaystyle B_{3}=\langle b_{3}^{*},b_{3}^{*}\rangle ={\begin{bmatrix}{\frac {-6}{14}}\\{\frac {9}{14}}\\{\frac {-3}{14}}\end{bmatrix}}{\begin{bmatrix}{\frac {-6}{14}}\\{\frac {9}{14}}\\{\frac {-3}{14}}\end{bmatrix}}={\frac {126}{196}}={\frac {9}{14}}}$
6. While ${\displaystyle k\leq 3}$ DO
1. Length reduce ${\displaystyle b_{3}}$ and correct ${\displaystyle \mu _{3,1}}$ and ${\displaystyle \mu _{3,2}}$

according to reduction subroutine in step 4: For ${\displaystyle \mid \mu _{3,1}\mid >{\frac {1}{2}}}$ EXECUTE reduction subroutine RED(3,1):

1. ${\displaystyle r=\lfloor 0.5+\mu _{3,l}\rfloor =5}$ and ${\displaystyle b_{3}=b_{3}-5b_{1}={\begin{bmatrix}3\\5\\6\end{bmatrix}}-{\begin{bmatrix}5\\5\\5\end{bmatrix}}={\begin{bmatrix}-2\\0\\1\end{bmatrix}}}$
2. ${\displaystyle \mu _{3,1}=\mu _{3,l}-r\mu _{1,1}={\frac {-1}{3}}\left(<{\frac {1}{2}}\right)}$
3. Set ${\displaystyle \mu _{3,1}=\mu _{3,1}-r={\frac {14}{3}}-5={\frac {-1}{3}}}$

For ${\displaystyle \mid \mu _{3,2}\mid >{\frac {1}{2}}}$ EXECUTE reduction subroutine RED(3,2):

1. ${\displaystyle r=\lfloor 0.5+\mu _{3,2}\rfloor =1}$ and ${\displaystyle b_{3}=b_{3}-b_{2}={\begin{bmatrix}3\\5\\6\end{bmatrix}}-{\begin{bmatrix}-1\\0\\2\end{bmatrix}}={\begin{bmatrix}4\\5\\4\end{bmatrix}}}$
2. Set ${\displaystyle \mu _{3,2}=\mu _{3,2}-r\mu _{2,2}={\frac {13}{14}}-1={\frac {-1}{14}}}$
3. ${\displaystyle \mu _{3,2}=\mu _{3,2}-1={\frac {-1}{14}}\left(<{\frac {1}{2}}\right)}$
2. As ${\displaystyle B_{3}<\left({\frac {3}{4}}-\mu _{3,2}^{2}\right)B_{2}}$ takes place, then
1. Exchange ${\displaystyle b_{3}}$ and ${\displaystyle b_{2}}$
2. ${\displaystyle k:=2}$

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

${\displaystyle {\begin{bmatrix}1&4&-1\\1&5&0\\1&4&2\end{bmatrix}}}$

Implement the algorithm steps again.

1. ${\displaystyle b_{1}^{*}=b_{1}={\begin{bmatrix}1\\1\\1\end{bmatrix}},B_{1}=3}$
2. ${\displaystyle \mu _{2,1}={\frac {\langle b_{2},b_{1}^{*}\rangle }{B_{1}}}={\frac {{\begin{bmatrix}4\\5\\4\end{bmatrix}}{\begin{bmatrix}1\\1\\1\end{bmatrix}}}{3}}={\frac {13}{3}}\left(>{\frac {1}{2}}\right)}$
3. ${\displaystyle b_{2}^{*}=b_{2}-\mu _{2,1}b_{1}^{*}={\begin{bmatrix}4\\5\\4\end{bmatrix}}-{\frac {13}{3}}{\begin{bmatrix}1\\1\\1\end{bmatrix}}={\begin{bmatrix}{\frac {-1}{3}}\\{\frac {2}{3}}\\{\frac {-1}{3}}\end{bmatrix}}}$.
4. ${\displaystyle B_{2}=\langle b_{2}^{*},b_{2}^{*}\rangle ={\frac {2}{3}}}$.
5. For ${\displaystyle \mid \mu _{2,1}\mid >{\frac {1}{2}}}$ EXECUTE reduction subroutine RED(2,1):
1. ${\displaystyle r=\lfloor 0.5+\mu _{2,l}\rfloor =4}$ and ${\displaystyle b_{2}=b_{2}-4b_{1}={\begin{bmatrix}4\\5\\4\end{bmatrix}}-{\begin{bmatrix}4\\4\\4\end{bmatrix}}={\begin{bmatrix}0\\1\\0\end{bmatrix}}}$
2. Set ${\displaystyle \mu _{2,1}=\mu _{2,1}-4\mu _{1,1}={\frac {13}{3}}-4={\frac {1}{3}}\left(<{\frac {1}{2}}\right)}$
6. As ${\displaystyle B_{2}<\left({\frac {3}{4}}-\mu _{2,1}^{2}\right)B_{1}}$ takes place, then
7. Exchange ${\displaystyle b_{2}}$ and ${\displaystyle b_{1}}$
OUTPUT:

LLL reduced basis

${\displaystyle {\begin{bmatrix}0&1&-1\\1&0&0\\0&1&2\end{bmatrix}}}$

## Applications

The LLL algorithm has found numerous other applications in MIMO detection algorithms [4] 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.[5]

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 ${\displaystyle R^{4}}$ spanned by ${\displaystyle [1,0,0,10000r^{2}],[0,1,0,10000r],}$ and ${\displaystyle [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 ${\displaystyle [a,b,c,10000(ar^{2}+br+c)]}$; but such a vector is "short" only if a, b, c are small and ${\displaystyle ar^{2}+br+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 ${\displaystyle 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