View source for LLL basis reduction method

Basis reduction is the process of transforming an arbitrary basis of a [[Lattice|lattice]] into a reduced basis, where a reduced basis consists of short vectors, or, equivalently, a basis that has a small orthogonality defect. Various notions of reduced basis have been proposed by Ch. Hermite [[#References|[a3]]], and by A. Korkin, G. Zolotarev and H. Minkowski in the language of quadratic forms (cf. also [[Geometry of numbers|Geometry of numbers]]; [[Quadratic form|Quadratic form]]). A.K. Lenstra, H.W. Lenstra and L. Lovász [[#References|[a5]]] introduced a notion of reduced lattice basis together with an efficient algorithm that transforms a given lattice basis into a reduced basis of the same lattice. This algorithm has found numerous applications in number theory and integer optimization, and various cryptographic schemes have been broken using this algorithm.

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l1101601.png" /> be the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l1101602.png" />-dimensional real vector space with inner product <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l1101603.png" /> and the Euclidean norm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l1101604.png" />. A lattice <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l1101605.png" /> is a discrete additive subgroup of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l1101606.png" /> (cf. [[Group|Group]]). Its rank or dimension is the dimension of the smallest linear subspace that contains <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l1101607.png" />. A lattice <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l1101608.png" /> of rank <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l1101609.png" /> has a basis, that is, a set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016010.png" /> linearly independent vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016011.png" />, so that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016012.png" /> consists of all linear integer combinations of the basis vectors, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016013.png" />.

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016014.png" /> be a basis of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016015.png" /> with basis matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016016.png" /> consisting of the column vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016017.png" />. Then all basis matrices of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016018.png" /> are of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016019.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016020.png" /> is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016021.png" /> integer matrix with determinant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016022.png" />.

With an ordered basis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016023.png" /> one can associate the Gram–Schmidt orthogonalization <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016024.png" />, which can be computed, together with the Gram–Schmidt coefficients <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016025.png" />, by the recursion <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016026.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016027.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016028.png" /> (cf. also [[Orthogonalization method|Orthogonalization method]]). A lattice basis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016029.png" /> is LLL-reduced if

1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016030.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016031.png" />;

2) for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016032.png" />,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016033.png" /></td> </tr></table>

For every LLL-reduced basis the length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016034.png" /> approximates the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016035.png" />th successive minimum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016036.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016037.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016038.png" /> is the smallest radius of a ball centred at the origin that contains <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016039.png" /> linearly independent lattice vectors. Always:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016040.png" /></td> </tr></table>

The novelty of LLL-reduction is a polynomial-time algorithm that transforms an arbitrary integer lattice basis into an LLL-reduced basis [[#References|[a5]]]. This algorithm has numerous applications.

For example, polynomials with integer coefficients <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016041.png" /> can be factored in polynomial time into irreducible factors [[#References|[a5]]]. There is a polynomial-time algorithm which, given a rational point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016042.png" /> and an integer lattice basis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016043.png" />, finds a lattice point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016044.png" /> that is nearest to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016045.png" /> up to a factor <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016046.png" /> [[#References|[a1]]]. Linear inequalities with integer coefficients in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016047.png" /> variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016048.png" /> can be solved over the integers in time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016049.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016050.png" /> is the maximal bit length of the entries in the inequalities [[#References|[a4]]], [[#References|[a6]]]. In particular, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016051.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016052.png" /> solutions of a single equation with integer coefficients can be found quite efficiently [[#References|[a2]]]. Univariate polynomial equations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016053.png" /> with an arbitrary integer modulus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016054.png" /> can be solved in polynomial time for small solutions, i.e., solutions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016055.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016056.png" />.

Some applications of LLL-reduction are possible because LLL-reduction can be refined to block reduction so that every reduced basis contains a vector that is not longer than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016057.png" /> times the shortest lattice vector, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016058.png" /> is fixed [[#References|[a8]]], [[#References|[a9]]]. Block reduction strongly reduces blocks <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016059.png" /> of the basis with fixed size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016060.png" />. LLL-reduction is the case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016061.png" />. The running time of block-reduction increases with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016062.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016063.png" /> approaches <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016064.png" />. Shortest lattice vectors of lattices of dimension up to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l110/l110160/l11016065.png" /> can be found within a few hours running time. LLL-reduction can be extended to reduce a set of linearly dependent real vectors. One can derive from LLL-reduction a continued fraction algorithm for arbitrary dimension [[#References|[a4]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  L. Babai,   "On Lovász lattice reduction and the nearest lattice point problem"  ''Combinatorica'' , '''6'''  (1986)  pp. 1–13</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  M.J. Coster,   A. Joux,   B.A. LaMacchia,   A.M. Odlyzko,   C.P. Schnorr,   J. Stern,   "An improved low-density subset sum algorithm"  ''Comp. Complexity'' , '''2'''  (1992)  pp. 111–128</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  C. Hermite,   "Extraits de lettres de M. Ch. Hermite á M. Jacobi sur différents objets de la théorie des nombres (2eme lettre du 6-8-1845)"  ''J. Reine Angew. Math.'' , '''40'''  (1850)  pp. 279–290</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  B. Just,   "Generalizing the continued fraction algorithm to arbitrary dimensions"  ''Siam J. Comput.'' , '''21'''  (1992)  pp. 909–926</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  R. Kannan,   "Minkowski's convex body theorem and integer programming"  ''Math. Oper. Res.'' , '''12'''  (1987)  pp. 415–440</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  A.K. Lenstra,   H.W. Lenstra, Jr.,   L. Lovász,   "Factoring polynomials with rational coefficients"  ''Math. Ann.'' , '''261'''  (1982)  pp. 515–534</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  H.W. Lenstra, Jr.,   "Integer programming with a fixed number of variables"  ''Math. Oper. Res.'' , '''8'''  (1983)  pp. 538–548</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  L. Lovász,   "An algorithmic theory of numbers, graphs and convexity" , SIAM  (1986)</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  C.P. Schnorr,   "A hierarchy of polynomial time lattice basis reduction algorithms"  ''Theor. Comput. Sci.'' , '''53'''  (1987)  pp. 201–224</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  C.P. Schnorr,   "Block reduced lattice bases and successive minima"  ''Combinatorics, Probab. Computing'' , '''3'''  (1994)  pp. 507–522</TD></TR></table>