﻿ Lenstra–Lenstra–Lovász lattice basis reduction algorithm - infoAnew

🤩 Discover new information from across the web

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

• ## Contents

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 ${\displaystyle B}$ is the largest length of ${\displaystyle \mathbf {b} _{i}}$ under the Euclidean norm, that is, ${\displaystyle B=\max \left(\Vert \mathbf {b} _{1}\Vert _{2},\Vert \mathbf {b} _{2}\Vert _{2},...,\Vert \mathbf {b} _{d}\Vert _{2}\right)}$ .[2][3]

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} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{n}\},}$

define its Gram–Schmidt process orthogonal basis

${\displaystyle \mathbf {B} ^{*}=\{\mathbf {b} _{1}^{*},\mathbf {b} _{2}^{*},\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 = 2,3,..,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 ${\displaystyle (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.[4] 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.

## Applications

An early successful application of the LLL algorithm was its use by Andrew Odlyzko and Herman te Riele in disproving Mertens conjecture.[5]

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

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 \mathbf {Z} ^{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....

## Properties of LLL-reduced basis

Let ${\displaystyle \mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{n}\}}$ be a ${\displaystyle \delta }$ -LLL-reduced basis of a lattice ${\displaystyle {\mathcal {L}}}$ . From the definition of LLL-reduced basis, we can derive several other useful properties about ${\displaystyle \mathbf {B} }$ .

1. The first vector in the basis cannot be much larger than the shortest non-zero vector: ${\displaystyle \Vert \mathbf {b} _{1}\Vert \leq (2/({\sqrt {4\delta -1}}))^{n-1}\cdot \lambda _{1}({\mathcal {L}})}$ . In particular, for ${\displaystyle \delta =3/4}$ , this gives ${\displaystyle \Vert \mathbf {b} _{1}\Vert \leq 2^{(n-1)/2}\cdot \lambda _{1}({\mathcal {L}})}$ .[8]
2. The first vector in the basis is also bounded by the determinant of the lattice: ${\displaystyle \Vert \mathbf {b} _{1}\Vert \leq (2/({\sqrt {4\delta -1}}))^{(n-1)/2}\cdot (\det({\mathcal {L}}))^{1/n}}$ . In particular, for ${\displaystyle \delta =3/4}$ , this gives ${\displaystyle \Vert \mathbf {b} _{1}\Vert \leq 2^{(n-1)/4}\cdot (\det({\mathcal {L}}))^{1/n}}$ .
3. The product of the norms of the vectors in the basis cannot be much larger than the determinant of the lattice: let ${\displaystyle \delta =3/4}$ , then ${\displaystyle \prod _{i=1}^{n}\Vert \mathbf {b} _{i}\Vert \leq 2^{n(n-1)/4}\cdot \det({\mathcal {L}})}$ .

## LLL algorithm pseudocode

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

INPUT
a lattice basis ${\displaystyle \mathbf {b} _{0},\mathbf {b} _{1},\ldots ,\mathbf {b} _{n}\in \mathbb {Z} ^{m}}$

a parameter ${\displaystyle \delta }$

with ${\displaystyle {\tfrac {1}{4}}<\delta <1}$

, most commonly ${\displaystyle \delta ={\tfrac {3}{4}}}$

PROCEDURE
${\displaystyle \mathbf {B^{\ast }} \gets {\rm {GramSchmidt}}(\{\mathbf {b} _{0},\ldots ,\mathbf {b} _{n}\})=\{\mathbf {b} _{0}^{\ast },\ldots ,\mathbf {b} _{n}^{\ast }\};}$

and do not normalize
${\displaystyle \mu _{i,j}\gets {\frac {\langle \mathbf {b} _{i},\mathbf {b} _{j}^{\ast }\rangle }{\langle \mathbf {b} _{j}^{\ast },\mathbf {b} _{j}^{\ast }\rangle }};}$

using the most current values of ${\displaystyle \mathbf {b} _{i}}$

and ${\displaystyle \mathbf {b} _{j}^{\ast }}$

${\displaystyle k\gets 1;}$

while ${\displaystyle k\leq n}$

do
for ${\displaystyle j}$

from ${\displaystyle k-1}$

to ${\displaystyle 0}$

do
if ${\displaystyle |\mu _{k,j}|>{\tfrac {1}{2}}}$

then
${\displaystyle \mathbf {b} _{k}\gets \mathbf {b} _{k}-\lfloor \mu _{k,j}\rceil \mathbf {b} _{j};}$

Update ${\displaystyle \mathbf {B^{\ast }} }$

and the related ${\displaystyle \mu _{i,j}}$

's as needed.
(The naive method is to recompute ${\displaystyle \mathbf {B^{\ast }} }$

whenever ${\displaystyle \mathbf {b} _{i}}$

changes:
${\displaystyle \mathbf {B^{\ast }} \gets {\rm {GramSchmidt}}(\{\mathbf {b} _{0},\ldots ,\mathbf {b} _{n}\})=\{\mathbf {b} _{0}^{\ast },\ldots ,\mathbf {b} _{n}^{\ast }\};}$

)
end if
end for
if ${\displaystyle \langle \mathbf {b} _{k}^{\ast },\mathbf {b} _{k}^{\ast }\rangle \geq \left(\delta -\mu _{k,k-1}^{2}\right)\langle \mathbf {b} _{k-1}^{\ast },\mathbf {b} _{k-1}^{\ast }\rangle }$

then
${\displaystyle k\gets k+1;}$

else
Swap ${\displaystyle \mathbf {b} _{k}}$

and  ${\displaystyle \mathbf {b} _{k-1};}$

Update ${\displaystyle \mathbf {B^{\ast }} }$

and the related ${\displaystyle \mu _{i,j}}$

's as needed.
${\displaystyle k\gets \max(k-1,1);}$

end if
end while
return ${\displaystyle \mathbf {B} }$

the LLL reduced basis of ${\displaystyle \{b_{0},\ldots ,b_{n}\}}$

OUTPUT
the reduced basis ${\displaystyle \mathbf {b} _{0},\mathbf {b} _{1},\ldots ,\mathbf {b} _{n}\in \mathbb {Z} ^{m}}$



## Examples

### Example from ${\displaystyle \mathbf {Z} ^{3}}$

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

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

then the reduced basis is

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

which is size-reduced, satisfies the Lovász condition, and is hence LLL-reduced, as described above. See W. Bosma.[10] for details of the reduction process.

### Example from ${\displaystyle \mathbf {Z} [i]^{4}}$

Likewise, for the basis over the complex integers given by the columns of the matrix below,

${\displaystyle {\begin{bmatrix}-2+2i&7+3i&7+3i&-5+4i\\3+3i&-2+4i&6+2i&-1+4i\\2+2i&-8+0i&-9+1i&-7+5i\\8+2i&-9+0i&6+3i&-4+4i\end{bmatrix}}}$ ,

then the columns of the matrix below give an LLL-reduced basis.

${\displaystyle {\begin{bmatrix}-6+3i&-2+2i&2-2i&-3+6i\\6-1i&3+3i&5-5i&2+1i\\2-2i&2+2i&-3-1i&-5+3i\\-2+1i&8+2i&7+1i&-2-4i\\\end{bmatrix}}}$ .

## 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
• Isabelle/HOL in the 'archive of formal proofs' entry LLL_Basis_Reduction. This code exports to efficiently executable Haskell.[11]

## Notes

1. ^ Lenstra, A. K.; Lenstra, H. W., Jr.; Lovász, L. (1982). "Factoring polynomials with rational coefficients". Mathematische Annalen. 261 (4): 515–534. CiteSeerX 10.1.1.310.318. doi:10.1007/BF01457454. hdl:1887/3810. MR 0682664.
2. ^ Galbraith, Steven (2012). "chapter 17". Mathematics of Public Key Cryptography.
3. ^ Nguyen, Phong Q.; Stehlè, Damien (September 2009). "An LLL Algorithm with Quadratic Complexity". SIAM J. Comput. 39 (3): 874–903. doi:10.1137/070705702. Retrieved 3 June 2019.
4. ^ Nguyen, Phong Q.; Stehlé, Damien (1 October 2009). "Low-dimensional lattice basis reduction revisited". ACM Transactions on Algorithms. 5 (4): 1–48. doi:10.1145/1597036.1597050.
5. ^ Odlyzko, Andrew; te Reile, Herman J. J. "Disproving Mertens Conjecture" (PDF). Journal für die reine und angewandte Mathematik. 357: 138–160. doi:10.1515/crll.1985.357.138. Retrieved 27 January 2020.
6. ^ Shahabuddin, Shahriar et al., "A Customized Lattice Reduction Multiprocessor for MIMO Detection", in Arxiv preprint, January 2015.
7. ^ D. Simon (2007). "Selected applications of LLL in number theory" (PDF). LLL+25 Conference. Caen, France.
8. ^ Regev, Oded. "Lattices in Computer Science: LLL Algorithm" (PDF). New York University. Retrieved 1 February 2019.
9. ^ Silverman, Joseph. "Introduction to Mathematical Cryptography Errata" (PDF). Brown University Mathematics Dept. Retrieved 5 May 2015.
10. ^ Bosma, Wieb. "4. LLL" (PDF). Lecture notes. Retrieved 28 February 2010.
11. ^ Divasón, Jose. "A Formalization of the LLL Basis Reduction Algorithm". Conference paper. Retrieved 3 May 2020.