Lenstra–Lenstra–Lovász lattice basis reduction algorithm

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

$$\backslash mathbf\{B\}=\backslash \{\; \backslash mathbf\{b\}\_1,\backslash mathbf\{b\}\_2,\; \backslash dots,\; \backslash mathbf\{b\}\_n\; \backslash \},$$

define its Gram–Schmidt process orthogonal basis

$$\backslash mathbf\{B\}^*=\backslash \{\; \backslash mathbf\{b\}^*\_1,\; \backslash mathbf\{b\}^*\_2,\; \backslash dots,\; \backslash mathbf\{b\}^*\_n\; \backslash \},$$

and the Gram-Schmidt coefficients

$$\backslash mu\_\{i,j\}=\backslash frac\{\backslash langle\backslash mathbf\{b\}\_i,\backslash mathbf\{b\}^*\_j\backslash rangle\}\{\backslash langle\backslash mathbf\{b\}^*\_j,\backslash mathbf\{b\}^*\_j\backslash rangle\},$$ for any .

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

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

\mathbf{b}^*_{k-1}\Vert^2.

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

An early successful application of the LLL algorithm was its use by Andrew Odlyzko and Herman te Riele in disproving Mertens conjecture.{{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}}

The LLL algorithm has found numerous other applications in MIMO detection algorithmsD. Wübben et al., "Lattice reduction," IEEE Signal Processing Magazine, Vol. 28, No. 3, pp. 70-91, Apr. 2011. 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.{{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}}

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 $\backslash mathbf\{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....

Let $\backslash mathbf\{B\}=\backslash \{\; \backslash mathbf\{b\}\_1,\backslash mathbf\{b\}\_2,\; \backslash dots,\; \backslash mathbf\{b\}\_n\; \backslash \}$ be a $\backslash delta$-LLL-reduced basis of a lattice $\backslash mathcal\; L$. From the definition of LLL-reduced basis, we can derive several other useful properties about $\backslash mathbf\{B\}$.

1. The first vector in the basis cannot be much larger than the shortest non-zero vector: $\backslash Vert\backslash mathbf\{b\}\_1\; \backslash Vert\; \backslash le\; (2\; /\; (\backslash sqrt\{4\backslash delta\; -\; 1\}))^\{n-1\}\; \backslash cdot\; \backslash lambda\_1(\backslash mathcal\; L)$. In particular, for $\backslash delta\; =\; 3/4$, this gives $\backslash Vert\backslash mathbf\{b\}\_1\; \backslash Vert\; \backslash le\; 2^\{(n-1)/2\}\; \backslash cdot\; \backslash lambda\_1(\backslash mathcal\; L)$.{{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}}
2. The first vector in the basis is also bounded by the determinant of the lattice: $\backslash Vert\backslash mathbf\{b\}\_1\; \backslash Vert\; \backslash le\; (2\; /\; (\backslash sqrt\{4\backslash delta\; -\; 1\}))^\{(n-1)/2\}\; \backslash cdot\; (\backslash det(\backslash mathcal\; L))^\{1/n\}$. In particular, for $\backslash delta\; =\; 3/4$, this gives $\backslash Vert\backslash mathbf\{b\}\_1\; \backslash Vert\; \backslash le\; 2^\{(n-1)/4\}\; \backslash cdot\; (\backslash det(\backslash 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 $\backslash delta\; =\; 3/4$, then $\backslash prod\_\{i=1\}^n\; \backslash Vert\backslash mathbf\{b\}\_i\; \backslash Vert\; \backslash le\; 2^\{n(n-1)/4\}\; \backslash cdot\; \backslash det(\backslash mathcal\; L)$.

The following description is based on {{harv|Hoffstein|Pipher|Silverman|2008|loc=Theorem 6.68}}, with the corrections from the errata.{{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}}

INPUT

a lattice basis b₁, b₂, ..., b_n in Z^m

a parameter δ with 1/4 < δ < 1, most commonly δ = 3/4

PROCEDURE

B^* <- GramSchmidt({b₁, ..., b_n}) = {b₁^*, ..., b_n^*}; and do not normalize

μ_i,j <- InnerProduct(b_i, b_j^*)/InnerProduct(b_j^*, b_j^*); using the most current values of b_i and b_j^*

k <- 2;

while k <= n do

for j from k−1 to 1 do

if |μ_k,j| > 1/2 then

b_k <- b_k − ⌊μ_k,j⌉b_j;

Update B^* and the related μ_i,j's as needed.

(The naive method is to recompute B^* whenever b_i changes:

B^* <- GramSchmidt({b₁, ..., b_n}) = {b₁^*, ..., b_n^*})

end if

end for

if InnerProduct(b_k^*, b_k^*) > (δ − μ²_k,k−1) InnerProduct(b_k−1^*, b_k−1^*) then

k <- k + 1;

else

Swap b_k and b_k−1;

Update B^* and the related μ_i,j's as needed.

k <- max(k−1, 2);

end if

end while

return B the LLL reduced basis of {b₁, ..., b_n}

OUTPUT

the reduced basis b₁, b₂, ..., b_n in Z^m

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

$$\backslash begin\{bmatrix\}$$

1 & -1& 3\\

1 & 0 & 5\\

1 & 2 & 6

\end{bmatrix}

then the reduced basis is

$$\backslash 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.{{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}} for details of the reduction process.

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

$$\backslash 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.

$$\backslash 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}.

LLL is implemented in

• [http://www.arageli.org/ Arageli] as the function lll_reduction_int
• [https://github.com/fplll/fplll fpLLL] as a stand-alone implementation
• FLINT as the function fmpz_lll
• 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
• [https://github.com/libntl/ntl Number Theory Library (NTL)] as the function LLL
• PARI/GP as the function qflll
• [http://pymatgen.org/ 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.{{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 }}

• Coppersmith method

{{Reflist}}

• {{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