LLL basis reduction method

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