View source for Lenstra–Lenstra–Lovász lattice basis reduction algorithm

{{Short description|Algorithm in computational number theory}}
{{Use dmy dates|date=July 2022}}
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.<ref>{{Cite journal|last1=Lenstra|first1=A. K.|author1-link=A. K. Lenstra|last2=Lenstra|first2=H. W. Jr.|author2-link=H. W. Lenstra, Jr.|last3=Lovász|first3=L.|author3-link=László Lovász|title=Factoring polynomials with rational coefficients|journal=[[Mathematische Annalen]]|volume=261| year=1982| issue=4|pages=515–534|hdl=1887/3810|doi=10.1007/BF01457454|mr=0682664|citeseerx=10.1.1.310.318|s2cid=5701340}}</ref> Given a [[basis (linear algebra)|basis]] <math>\mathbf{B} = \{ \mathbf{b}_1,\mathbf{b}_2, \dots, \mathbf{b}_d \}</math> with ''n''-dimensional integer coordinates, for a [[lattice (group)|lattice]] L (a discrete subgroup of  '''R'''<sup>''n''</sup>) with <math> d \leq n </math>, the LLL algorithm calculates an ''LLL-reduced'' (short, nearly [[orthogonal]]) lattice basis in time <math display="block">\mathcal O(d^5n\log^3 B)</math> where <math>B</math> is the largest length of <math>\mathbf{b}_i</math> under the [[Norm_(mathematics)#Euclidean_norm |Euclidean norm]], that is, <math>B = \max\left(\|\mathbf{b}_1\|_2, \|\mathbf{b}_2\|_2, \dots, \|\mathbf{b}_d\|_2\right)</math>.<ref>{{Cite book|last1=Galbraith|first1=Steven|title=Mathematics of Public Key Cryptography| year=2012|chapter=chapter 17|chapter-url=https://www.math.auckland.ac.nz/~sgal018/crypto-book/crypto-book.html}}</ref><ref>{{cite journal |last1=Nguyen |first1=Phong Q. |last2=Stehlè |first2=Damien |title=An LLL Algorithm with Quadratic Complexity |journal=SIAM J. Comput. |date=September 2009 |volume=39 |issue=3 |pages=874–903 |doi=10.1137/070705702 |url=https://dl.acm.org/citation.cfm?id=1655318 |access-date=3 June 2019}}</ref>

The original applications were to give polynomial-time algorithms for [[Polynomial factorization#Factoring univariate polynomials over the integers|factorizing polynomials with rational coefficients]], for finding [[Dirichlet's approximation theorem#Simultaneous Version|simultaneous rational approximations to real numbers]], and for solving the [[linear programming|integer linear programming problem]] in fixed dimensions.

==LLL reduction==
The precise definition of LLL-reduced is as follows: Given a [[Basis (linear algebra)|basis]]
<math display="block">\mathbf{B}=\{ \mathbf{b}_1,\mathbf{b}_2, \dots, \mathbf{b}_n \},</math>
define its [[Gram–Schmidt process]] orthogonal basis
<math display="block">\mathbf{B}^*=\{ \mathbf{b}^*_1, \mathbf{b}^*_2, \dots, \mathbf{b}^*_n \},</math>
and the Gram-Schmidt coefficients
<math display="block">\mu_{i,j}=\frac{\langle\mathbf{b}_i,\mathbf{b}^*_j\rangle}{\langle\mathbf{b}^*_j,\mathbf{b}^*_j\rangle},</math> for any <math>1 \le j < i \le n</math>.

Then the basis <math>B</math> is LLL-reduced if there exists a parameter <math>\delta</math> in {{open-closed|0.25, 1}} such that the following holds:

# (size-reduced) For <math>1 \leq j < i \leq n\colon \left|\mu_{i,j}\right|\leq 0.5</math>. By definition, this property guarantees the length reduction of the ordered basis.
#  (Lovász condition) For k = 2,3,..,n <math>  \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</math>.

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

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.<ref>{{Cite journal|last1=Nguyen|first1=Phong Q.|last2=Stehlé|first2=Damien|date=1 October 2009|title=Low-dimensional lattice basis reduction revisited |journal=ACM Transactions on Algorithms |language=en|volume=5|issue=4|pages=1–48|doi=10.1145/1597036.1597050|s2cid=10583820}}</ref> However, an LLL-reduced basis is nearly as short as possible, in the sense that there are absolute bounds <math>c_i > 1</math> such that the first basis vector is no more than <math>c_1</math> times as long as a shortest vector in the lattice,
the second basis vector is likewise within <math>c_2</math> 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]].<ref>{{cite journal |last1=Odlyzko |first1=Andrew |last2=te Reile |first2=Herman J. J. |title=Disproving Mertens Conjecture |journal=[[Journal für die reine und angewandte Mathematik]] |volume=357 |pages=138–160 |doi=10.1515/crll.1985.357.138 |s2cid=13016831 |url=http://www.dtc.umn.edu/~odlyzko/doc/arch/mertens.disproof.pdf |access-date=27 January 2020}}</ref>

The LLL algorithm has found numerous other applications in [[MIMO]] detection algorithms<ref>D. Wübben et al., "Lattice reduction," IEEE Signal Processing Magazine, Vol. 28, No. 3, pp. 70-91, Apr. 2011.</ref> and cryptanalysis of [[public-key encryption]] schemes: [[Naccache-Stern knapsack cryptosystem|knapsack cryptosystems]], [[RSA (algorithm)|RSA]] with particular settings, [[NTRUEncrypt]], and so forth. The algorithm can be used to find integer solutions to many problems.<ref>{{Cite journal| author=D. Simon |title=Selected applications of LLL in number theory |journal=LLL+25 Conference |year=2007 |place=Caen, France | url=https://simond.users.lmno.cnrs.fr/maths/lll25_Simon.pdf}}</ref>

In particular, the LLL algorithm forms a core of one of the [[integer relation algorithm]]s. For example, if it is believed that ''r''=1.618034 is a (slightly rounded) [[Root of a function|root]] to an unknown [[quadratic equation]] with integer coefficients, one may apply LLL reduction to the lattice in <math>\mathbf{R}^4</math> spanned by <math>[1,0,0,10000r^2], [0,1,0,10000r],</math> and <math>[0,0,1,10000]</math>. The first vector in the reduced basis will be an integer [[linear combination]] of these three, thus necessarily of the form <math>[a,b,c,10000(ar^2+br+c)]</math>; but such a vector is "short" only if ''a'', ''b'', ''c'' are small and <math>ar^2+br+c</math> 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 <math>x^2-x-1</math> has a root equal to the [[golden ratio]], 1.6180339887....

==Properties of LLL-reduced basis==
Let <math>\mathbf{B}=\{ \mathbf{b}_1,\mathbf{b}_2, \dots, \mathbf{b}_n \}</math> be a <math>\delta</math>-LLL-reduced basis of a [[Lattice (group)|lattice]] <math>\mathcal L</math>. From the definition of LLL-reduced basis, we can derive several other useful properties about <math>\mathbf{B}</math>.

# The first vector in the basis cannot be much larger than the [[Lattice problem#Shortest vector problem (SVP)|shortest non-zero vector]]: <math>\Vert\mathbf{b}_1 \Vert \le (2 / (\sqrt{4\delta - 1}))^{n-1} \cdot \lambda_1(\mathcal L)</math>. In particular, for <math>\delta = 3/4</math>, this gives <math>\Vert\mathbf{b}_1 \Vert \le 2^{(n-1)/2} \cdot \lambda_1(\mathcal L)</math>.<ref name="regev_lll">{{cite web |last1=Regev |first1=Oded |title=Lattices in Computer Science: LLL Algorithm |url=https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/lll.pdf#page=3 |publisher=New York University |access-date=1 February 2019}}</ref>
# The first vector in the basis is also bounded by the determinant of the lattice: <math>\Vert\mathbf{b}_1 \Vert \le (2 / (\sqrt{4\delta - 1}))^{(n-1)/2} \cdot (\det(\mathcal L))^{1/n}</math>. In particular, for <math>\delta = 3/4</math>, this gives <math>\Vert\mathbf{b}_1 \Vert \le 2^{(n-1)/4} \cdot  (\det(\mathcal L))^{1/n}</math>.
# The product of the norms of the vectors in the basis cannot be much larger than the determinant of the lattice: let <math>\delta = 3/4</math>, then  <math display="inline">\prod_{i=1}^n \Vert\mathbf{b}_i \Vert \le 2^{n(n-1)/4} \cdot  \det(\mathcal L)</math>.

==LLL algorithm pseudocode==
The following description is based on {{harv|Hoffstein|Pipher|Silverman|2008|loc=Theorem 6.68}}, with the corrections from the errata.<ref>{{cite web| last1=Silverman| first1=Joseph| title=Introduction to Mathematical Cryptography Errata|url=http://www.math.brown.edu/~jhs/MathCrypto/MathCryptoErrata.pdf|website=Brown University Mathematics Dept.| access-date=5 May 2015}}</ref>

 '''INPUT'''
     a lattice basis '''b'''<sub>1</sub>, '''b'''<sub>2</sub>, ..., '''b'''<sub>''n''</sub> in '''Z'''<sup>''m''</sup>
     a parameter ''δ'' with 1/4 < ''δ'' < 1, most commonly ''δ'' = 3/4
 '''PROCEDURE'''
     '''B<sup>*</sup>''' <- GramSchmidt({'''b'''<sub>1</sub>, ..., '''b'''<sub>''n''</sub>}) = {'''b'''<sub>1</sub><sup>*</sup>, ..., '''b'''<sub>''n''</sub><sup>*</sup>};  ''and do not normalize''
     ''μ''<sub>''i'',''j''</sub> <- InnerProduct('''b'''<sub>''i''</sub>, '''b'''<sub>''j''</sub><sup>*</sup>)/InnerProduct('''b'''<sub>j</sub><sup>*</sup>, '''b'''<sub>''j''</sub><sup>*</sup>);   ''using the most current values of'' '''b'''<sub>''i''</sub> and '''b'''<sub>''j''</sub><sup>*</sup>
     ''k'' <- 2;
     '''while''' ''k'' <= ''n'' '''do'''
         '''for''' ''j'' '''from''' ''k''−1 '''to''' 1 '''do'''
             '''if''' |''μ''<sub>''k'',''j''</sub>| > 1/2 '''then'''
                 '''b'''<sub>''k''</sub> <- '''b'''<sub>''k''</sub> − ⌊''μ''<sub>''k'',''j''</sub>⌉'''b'''<sub>''j''</sub>;
                ''Update'' '''B<sup>*</sup>''' ''and the related'' ''μ''<sub>''i'',''j''</sub>''<nowiki/>'s as needed.''
                ''(The naive method is to recompute'' '''B<sup>*</sup>''' ''whenever'' '''b<sub>''i''</sub>''' ''changes:''
                 '''B<sup>*</sup>''' <- GramSchmidt({'''b'''<sub>1</sub>, ..., '''b'''<sub>''n''</sub>}) = {'''b'''<sub>1</sub><sup>*</sup>, ..., '''b'''<sub>''n''</sub><sup>*</sup>})
             '''end if'''
         '''end for'''
         '''if''' InnerProduct('''b'''<sub>''k''</sub><sup>*</sup>, '''b'''<sub>''k''</sub><sup>*</sup>) > (''δ − μ<sup>2</sup>''<sub>''k'',''k''−1</sub>) InnerProduct('''b'''<sub>''k''−1</sub><sup>*</sup>, '''b'''<sub>''k''−1</sub><sup>*</sup>) '''then'''
             ''k'' <- ''k'' + 1;
         '''else'''
             Swap '''b'''<sub>''k''</sub> and  '''b'''<sub>''k''−1</sub>;
             ''Update'' '''B<sup>*</sup>''' ''and the related'' ''μ''<sub>''i'',''j''</sub>''<nowiki/>'s as needed.''
             ''k'' <- max(''k''−1, 2);
         '''end if'''
     '''end while'''
     '''return''' '''B''' the LLL reduced basis of {b<sub>1</sub>, ..., b<sub>''n''</sub>}
 '''OUTPUT'''
     the reduced basis '''b'''<sub>1</sub>, '''b'''<sub>2</sub>, ..., '''b'''<sub>''n''</sub> in '''Z'''<sup>''m''</sup>

==Examples==
=== Example from Z<sup>3</sup> ===

Let a lattice basis <math> \mathbf{b}_1,\mathbf{b}_2, \mathbf{b}_3 \in \mathbf{Z}^{3}</math>, be given by the columns of
<math display="block">\begin{bmatrix}
  1 & -1& 3\\
  1 & 0 & 5\\
  1 & 2 & 6
\end{bmatrix}</math>
then the reduced basis is 
<math display="block">\begin{bmatrix}
  0 & 1& -1\\
  1 & 0 & 0\\
  0 & 1 & 2
\end{bmatrix},</math>
which is size-reduced, satisfies the Lovász condition, and is hence LLL-reduced, as described above. See W. Bosma.<ref>{{Cite web| url=http://www.math.ru.nl/~bosma/onderwijs/voorjaar07/compalg7.pdf|title=4. LLL |last=Bosma|first=Wieb|work=Lecture notes|access-date=28 February 2010}}</ref> for details of the reduction process.

=== Example from Z[''i'']<sup>4</sup> ===
Likewise, for the basis over the complex integers given by the columns of the matrix below,
<math display="block">\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},</math>
then the columns of the matrix below give an LLL-reduced basis. 
<math display="block">\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}.</math>

==Implementations==
LLL is implemented in
*[http://www.arageli.org/ Arageli] as the function <code>lll_reduction_int</code>
*[https://github.com/fplll/fplll fpLLL] as a stand-alone implementation
*[[Fast Library for Number Theory|FLINT]] as the function <code>fmpz_lll</code>
*[[GAP computer algebra system|GAP]] as the function <code>LLLReducedBasis</code>
*[[Macaulay2]] as the function <code>LLL</code> in the package <code>LLLBases</code>
*[[Magma computer algebra system|Magma]] as the functions <code>LLL</code> and <code>LLLGram</code> (taking a gram matrix)
*[[Maple computer algebra system|Maple]] as the function <code>IntegerRelations[LLL]</code>
*[[Mathematica]] as the function <code>LatticeReduce</code>
*[https://github.com/libntl/ntl Number Theory Library (NTL)] as the function <code>LLL</code>
*[[PARI/GP]] as the function <code>qflll</code>
*[http://pymatgen.org/ Pymatgen] as the function <code>analysis.get_lll_reduced_lattice</code>
*[[SageMath]] as the method <code>LLL</code> driven by fpLLL and NTL
*[[Isabelle/HOL]] in the 'archive of formal proofs' entry <code>LLL_Basis_Reduction</code>. This code exports to efficiently executable Haskell.<ref>{{Cite book|chapter=A Formalization of the LLL Basis Reduction Algorithm |last=Divasón|first=Jose|title= Interactive Theorem Proving: 9th International Conference, ITP 2018, Held as Part of the Federated Logic Conference, FloC 2018, Oxford, UK, July 9–12, 2018, Proceedings|series=Lecture Notes in Computer Science |year=2018 |volume=10895 |pages=160–177 |doi=10.1007/978-3-319-94821-8_10 |isbn=978-3-319-94820-1 |doi-access=free }}</ref>

==See also==
*[[Coppersmith method]]

==Notes==
{{Reflist}}

==References==
* {{cite journal|first1=Huguette |last1=Napias
|title=A generalization of the LLL algorithm over euclidean rings or orders
|journal=Journal de Théorie des Nombres de Bordeaux
|volume=8
|number=2
|year=1996
|pages=387–396
|url=http://www.numdam.org/item?id=JTNB_1996__8_2_387_0
|doi=10.5802/jtnb.176
|doi-access=free
}}
* {{Cite book|last=Cohen|first=Henri|title=A course in computational algebraic number theory|publisher=Springer|year=2000|series=GTM|volume=138|isbn=3-540-55640-0}}
* {{Cite book| last=Borwein | first=Peter | author-link=Peter Borwein | title=Computational Excursions in Analysis and Number Theory | isbn=0-387-95444-9 | year=2002| publisher=Springer }}
* {{cite journal|first1=Franklin T. |last1=Luk| first2=Sanzheng |last2=Qiao|title=A pivoted LLL algorithm|journal= Linear Algebra and Its Applications|year=2011
|volume=434
|issue=11|doi=10.1016/j.laa.2010.04.003
|pages=2296–2307
|doi-access=free}}
* {{cite book
|last1=Hoffstein |first1=Jeffrey
|last2=Pipher    |first2=Jill
|last3=Silverman |first3=J.H.
|title=An Introduction to Mathematical Cryptography
|year=2008
|publisher=Springer
|isbn=978-0-387-77993-5
}}
{{Number-theoretic algorithms}}

{{DEFAULTSORT:Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm}}
[[Category:Theory of cryptography]]
[[Category:Computational number theory]]
[[Category:Lattice points]]