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 be the -dimensional real vector space with inner product and the Euclidean norm . A lattice is a discrete additive subgroup of (cf. Group). Its rank or dimension is the dimension of the smallest linear subspace that contains . A lattice of rank has a basis, that is, a set of linearly independent vectors , so that consists of all linear integer combinations of the basis vectors, .

Let be a basis of with basis matrix consisting of the column vectors . Then all basis matrices of are of the form , where is an integer matrix with determinant .

With an ordered basis one can associate the Gram–Schmidt orthogonalization , which can be computed, together with the Gram–Schmidt coefficients , by the recursion , for (cf. also Orthogonalization method). A lattice basis is LLL-reduced if

1) for ;

2) for ,

For every LLL-reduced basis the length approximates the th successive minimum of , where is the smallest radius of a ball centred at the origin that contains linearly independent lattice vectors. Always:

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 can be factored in polynomial time into irreducible factors [a5]. There is a polynomial-time algorithm which, given a rational point and an integer lattice basis , finds a lattice point that is nearest to up to a factor [a1]. Linear inequalities with integer coefficients in variables can be solved over the integers in time , where is the maximal bit length of the entries in the inequalities [a4], [a6]. In particular, - solutions of a single equation with integer coefficients can be found quite efficiently [a2]. Univariate polynomial equations with an arbitrary integer modulus can be solved in polynomial time for small solutions, i.e., solutions with .

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 times the shortest lattice vector, where is fixed [a8], [a9]. Block reduction strongly reduces blocks of the basis with fixed size . LLL-reduction is the case . The running time of block-reduction increases with as approaches . Shortest lattice vectors of lattices of dimension up to 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