# LLL basis reduction method

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Basis reduction is the process of transforming an arbitrary basis of a 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 [a3], and by A. Korkin, G. Zolotarev and H. Minkowski in the language of quadratic forms (cf. also Geometry of numbers; Quadratic form). A.K. Lenstra, H.W. Lenstra and L. Lovász [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). 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). 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 [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 [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 } }$[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 [a4], [a6]. In particular, $0$- $1$ solutions of a single equation with integer coefficients can be found quite efficiently [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 [a8], [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 [a4].

#### References

 [a1] L. Babai, "On Lovász lattice reduction and the nearest lattice point problem" Combinatorica , 6 (1986) pp. 1–13 MR0856638 Zbl 0593.68030 [a2] 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 MR1227795 Zbl 0774.11075 [a3] 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 [a4] B. Just, "Generalizing the continued fraction algorithm to arbitrary dimensions" Siam J. Comput. , 21 (1992) pp. 909–926 MR1181407 Zbl 0763.11027 [a5] R. Kannan, "Minkowski's convex body theorem and integer programming" Math. Oper. Res. , 12 (1987) pp. 415–440 [a6] A.K. Lenstra, H.W. Lenstra, Jr., L. Lovász, "Factoring polynomials with rational coefficients" Math. Ann. , 261 (1982) pp. 515–534 MR0682664 Zbl 0488.12001 Zbl 0477.68043 [a7] H.W. Lenstra, Jr., "Integer programming with a fixed number of variables" Math. Oper. Res. , 8 (1983) pp. 538–548 MR0727410 Zbl 0524.90067 [a8] L. Lovász, "An algorithmic theory of numbers, graphs and convexity" , SIAM (1986) MR0861822 Zbl 0606.68039 [a9] C.P. Schnorr, "A hierarchy of polynomial time lattice basis reduction algorithms" Theor. Comput. Sci. , 53 (1987) pp. 201–224 MR0918090 Zbl 0642.10030 [a10] C.P. Schnorr, "Block reduced lattice bases and successive minima" Combinatorics, Probab. Computing , 3 (1994) pp. 507–522 MR1314072 Zbl 0845.11025
How to Cite This Entry:
LLL basis reduction method. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=LLL_basis_reduction_method&oldid=47549
This article was adapted from an original article by C.P. Schnorr (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article