# 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 $\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 $\ d \leq n$, the LLL algorithm calculates an LLL-reduced (short, nearly orthogonal) lattice basis in time

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

where B is the largest length of $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

$\mathbf{B}=\{ \mathbf{b}_0,\mathbf{b}_1, \dots, \mathbf{b}_n \},$

define its Gram–Schmidt process orthogonal basis

$\mathbf{B}^*=\{ \mathbf{b}^*_0, \mathbf{b}^*_1, \dots, \mathbf{b}^*_n \},$

and the Gram-Schmidt coefficients

$\mu_{i,j}=\frac{\langle\mathbf{b}_i,\mathbf{b}^*_j\rangle}{\langle\mathbf{b}^*_j,\mathbf{b}^*_j\rangle}$, for any $1 \le j < i \le n$.

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

1. (size-reduced) For $1 \leq j < i \leq n\colon \left|\mu_{i,j}\right|\leq 0.5$. By definition, this property guarantees the length reduction of the ordered basis.
2. (Lovász condition) For k = 1,2,..,n $\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 $\delta$ parameter, we can conclude how well the basis is reduced. Greater values of $\delta$ lead to stronger reductions of the basis. Initially, A. Lenstra, H. Lenstra and L. Lovász demonstrated the LLL-reduction algorithm for $\delta = \frac{3}{4}$. Note that although LLL-reduction is well-defined for $\delta = 1$, the polynomial-time complexity is guaranteed only for $\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. 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 [2]

INPUT:

$\triangleright$ a lattice basis $b_0, b_1, \dots, b_n \in Z^{m}$,
$\triangleright$ parameter $\delta$ with $\frac{1}{4} < \delta <1$, most commonly $\delta = \frac{3}{4}$

PROCEDURE:

   Perform Gram-Schmidt, but do not normalize:
$ortho := gramSchmidt(\{b_0, \dots, b_n\}) = \{ b_0^*, \dots, b_n^* \}$
Define $\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 $b_i, b_j^*$.
Let $k=1$
while $k \le n$ do
for $j$ from $k-1$ to $0$ do
if $|\mu_{k,j}| > \frac{1}{2}$ do
$b_k = b_k - \lfloor \mu_{k,j} \rceil b_j$
Update $ortho$ entries and related $\mu_{i,j}$'s as needed.
(The naive method is to recompute $ortho := gramSchmidt(\{b_0, \dots, b_n\}) = \{ b_0^*, \dots, b_n^* \}$ whenever a $b_i$ changes.)
end if
end for
if $\langle b_k^*, b_k^*\rangle \ge (\delta - (\mu_{k,k-1})^2)\langle b_{k-1}^*, b_{k-1}^*\rangle$ do
$k = k + 1$
else do
Swap $b_k$ and $b_{k-1}$.
Update $ortho$ entries and related $\mu_{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, \dots, b_n$

## Example

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

INPUT:

Let a lattice basis $\mathbf{b}_1,\mathbf{b}_2, \mathbf{b}_3 \in Z^{3}$, be given by the columns of

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

Then according to the LLL algorithm we obtain the following:

1.$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 $i=2$ DO:

2.1.For $j=1$ set $\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}(< \frac{1}{2})$

and $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.2$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. $\mathbf{k}:=2$

4.Here the step 4 of the LLL algorithm is skipped as size-reduced property holds for $\mu_{2,1}$

5.For $i=3$ and for $j=1,2$ calculate $\mu_{i,j}$ and $B_{i}$: $\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 $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 $\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}(> \frac{1}{2})$

hence $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

$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 $k \leq 3$ DO

6.1 Length reduce $b_{3}$ and correct $\mu_{3,1}$ and $\mu_{3,2}$ according to reduction subroutine in step 4:

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

i.$r = \lfloor 0.5 + \mu_{3,l} \rfloor =5$ and $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}$

ii.$\mu_{3,1}= \mu_{3,l} - r\mu_{1,1} = \frac{-1}{3}(< \frac{1}{2})$

iii.Set $\mu_{3,1}= \mu_{3,1} - r= \frac{14}{3}-5= \frac{-1}{3}$

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

i.$r = \lfloor 0.5 + \mu_{3,2} \rfloor =1$ and $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}$

ii.Set $\mu_{3,2}= \mu_{3,2} - r\mu_{2,2}= \frac{13}{14}-1= \frac{-1}{14}$

iii.$\mu_{3,2}= \mu_{3,2} - 1 = \frac{-1}{14}(< \frac{1}{2})$

6.2 As $B_{3} < (\frac{3}{4}- \mu_{3,2}^2)B_{2}$ takes place, then

6.2.1 Exchange $b_{3}$ and $b_{2}$

6.2.2 $k$:= 2

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

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

Implement the algorithm steps again. 1.$b_{1}^{*}= b_{1}= \begin{bmatrix}1\\1\\1\end{bmatrix},B_{1}= 3$

2. $\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}(>\frac{1}{2})$

3.$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.$B_{2}= \langle b_{2}^{*}, b_{2}^{*} \rangle = \frac{2}{3}$.

5.For $\mid \mu_{2,1}\mid >\frac{1}{2}$ EXECUTE reduction subroutine RED(2,1):

i.$r = \lfloor 0.5 + \mu_{2,l} \rfloor =4$ and $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}$

ii.Set $\mu_{2,1}= \mu_{2,1} - 4\mu_{1,1}= \frac{13}{3}- 4= \frac{1}{3}(< \frac{1}{2})$

6. As $B_{2} < (\frac{3}{4}- \mu_{2,1}^2)B_{1}$ takes place, then

7. Exchange $b_{2}$ and $b_{1}$

OUTPUT: LLL reduced basis

$\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 $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 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
• Sage as the method LLL driven by fpLLL and NTL