View source for LLL basis reduction method

<!--
l1101601.png
$#A+1 = 65 n = 0
$#C+1 = 65 : ~/encyclopedia/old_files/data/L110/L.1100160 LLL basis reduction method
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

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  $  \mathbf R  ^ {n} $
be the  $  n $-
dimensional real vector space with inner product  $  \langle  {\cdot, \cdot } \rangle $
and the Euclidean norm  $  \| y \| = \langle  {y,y } \rangle ^ { {1 / 2 } } $. 
A lattice  $  L \subset  \mathbf R  ^ {n} $
is a discrete additive subgroup of  $  \mathbf R  ^ {n} $(
cf. [[Group|Group]]). Its rank or dimension is the dimension of the smallest linear subspace that contains  $  L $. 
A lattice  $  L $
of rank  $  m $
has a basis, that is, a set of  $  m $
linearly independent vectors  $  b _ {1} \dots b _ {m} $, 
so that  $  L $
consists of all linear integer combinations of the basis vectors,  $  L = \{ {t _ {1} b _ {1} + \dots + t _ {m} b _ {m} } : {t _ {1} \dots t _ {m} \in \mathbf Z } \} $.

Let  $  b _ {1} \dots b _ {m} \in \mathbf R  ^ {n} $
be a basis of  $  L $
with basis matrix  $  B = [ b _ {1} \dots b _ {m} ] $
consisting of the column vectors  $  b _ {1} \dots b _ {m} $. 
Then all basis matrices of  $  L $
are of the form  $  {\overline{B}\; } = BM $, 
where  $  M $
is an  $  ( m \times m ) $
integer matrix with determinant  $  \pm  1 $.

With an ordered basis  $  b _ {1} \dots b _ {m} \in \mathbf R  ^ {n} $
one can associate the Gram–Schmidt orthogonalization  $  {\widehat{b}  } _ {1} \dots {\widehat{b}  } _ {m} \in \mathbf R  ^ {n} $, 
which can be computed, together with the Gram–Schmidt coefficients  $  \mu _ {i,j }  = { {\langle  {b _ {i} , {\widehat{b}  } _ {j} } \rangle } / {\langle  { {\widehat{b}  } _ {j} , {\widehat{b}  } _ {j} } \rangle } } $, 
by the recursion  $  {\widehat{b}  } _ {1} = b _ {1} $, 
$  {\widehat{b}  } _ {i} = b _ {i} - \sum _ {j = 1 }  ^ {i - 1 } \mu _ {i,j }  {\widehat{b}  } _ {j} $
for  $  i = 2 \dots m $(
cf. also [[Orthogonalization method|Orthogonalization method]]). A lattice basis  $  b _ {1} \dots b _ {m} $
is LLL-reduced if

1)  $  | {\mu _ {i,j }  } | \leq  {1 / 2 } $
for  $  1 \leq  j < i \leq  m $;

2) for  $  1 < i \leq  m $,

$$ 
{
\frac{3}{4}
 } \left \| { {\widehat{b}  } _ {i - 1 }  } \right \|  ^ {2} \leq  \left \| { {\widehat{b}  } _ {i} + \mu _ {i,i - 1 }  {\widehat{b}  } _ {i + 1 }  } \right \|  ^ {2} .
$$

For every LLL-reduced basis the length  $  \| {b _ {i} } \| $
approximates the  $  i $
th successive minimum  $  \lambda _ {i} $
of  $  L $, 
where  $  \lambda _ {i} ( L ) $
is the smallest radius of a ball centred at the origin that contains  $  i $
linearly independent lattice vectors. Always:

$$ 
2 ^ {1 - i } \leq  \left \| { {\widehat{b}  } _ {i} } \right \|  ^ {2} \lambda _ {i} ( L ) ^ {- 2 } \leq  \left \| {b _ {i} } \right \|  ^ {2} \lambda _ {i} ( L ) ^ {- 2 } \leq  2 ^ {m - 1 } .
$$

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  $  c _ {0} + c _ {1} x + \dots + c _ {n} x  ^ {n} $
can be factored in polynomial time into irreducible factors [[#References|[a5]]]. There is a polynomial-time algorithm which, given a rational point  $  x \in \mathbf R  ^ {n} $
and an integer lattice basis  $  b _ {1} \dots b _ {m} $, 
finds a lattice point  $  b $
that is nearest to  $  x $
up to a factor  $  2 ^ { {n / 2 } } $[[#References|[a1]]]. Linear inequalities with integer coefficients in  $  n $
variables  $  x _ {1} \dots x _ {n} $
can be solved over the integers in time  $  n ^ {O ( n ) } M ^ {O ( 1 ) } $, 
where  $  M $
is the maximal bit length of the entries in the inequalities [[#References|[a4]]], [[#References|[a6]]]. In particular,  $  0 $-
$  1 $
solutions of a single equation with integer coefficients can be found quite efficiently [[#References|[a2]]]. Univariate polynomial equations  $  p ( x ) = 0 ( { \mathop{\rm mod} } N ) $
with an arbitrary integer modulus  $  N $
can be solved in polynomial time for small solutions, i.e., solutions  $  x $
with  $  | x | \leq  O ( N ^ { {1 / 4 } } ) $.

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  $  ( 1 + \epsilon )  ^ {n} $
times the shortest lattice vector, where  $  \epsilon > 0 $
is fixed [[#References|[a8]]], [[#References|[a9]]]. Block reduction strongly reduces blocks  $  b _ {i} \dots b _ {i + \beta - 1 }  $
of the basis with fixed size  $  \beta $. 
LLL-reduction is the case  $  \beta = 2 $. 
The running time of block-reduction increases with  $  \beta $
as  $  \epsilon $
approaches  $  0 $. 
Shortest lattice vectors of lattices of dimension up to  $  80 $
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 {{MR|0856638}} {{ZBL|0593.68030}} </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 {{MR|1227795}} {{ZBL|0774.11075}} </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 {{MR|1181407}} {{ZBL|0763.11027}} </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 {{MR|0682664}} {{ZBL|0488.12001}} {{ZBL|0477.68043}} </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 {{MR|0727410}} {{ZBL|0524.90067}} </TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top"> L. Lovász, "An algorithmic theory of numbers, graphs and convexity" , SIAM (1986) {{MR|0861822}} {{ZBL|0606.68039}} </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 {{MR|0918090}} {{ZBL|0642.10030}} </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 {{MR|1314072}} {{ZBL|0845.11025}} </TD></TR></table>