zbMATH — the first resource for mathematics

A modification of the LLL reduction algorithm. (English) Zbl 0629.10001
This paper gives a modification of the Lenstra, Lenstra, Lovasz algorithm (LLL) for finding a basis of “small” vectors in a lattice \(L\subset {\mathbb{R}}^ n\). In the original LLL algorithm it is assumed that L is given by a set of basic vectors. The modified algorithm can also deal with the case that L is given by a set of generating vectors, that are not necessarily independent. In fact, if the generators are not independent, the algorithm first computes a set of basic vectors for L and in a second run a basis that contains small vectors of L is computed.
The modification given here extends proposals of other authors for computing the basis, using the LLL algorithm. The basic idea for the modification is to see the given lattice L as a projection of a lattice L’ in a higher dimensional space \({\mathbb{R}}^{n+m}\). In fact the given generators are projections of a set of basic vectors of L’. By the LLL algorithm a basis \({\mathcal B}\) of L’ is computed. If the lattice L’ is chosen in the right way, the projection of L to L’ maps \({\mathcal B}\) onto a basis of L. Several elements of \({\mathcal B}\) may map to \({\mathfrak O}\), in which case they represent nontrivial relations between the given generators of L.
The problem of choosing the right lattice L’ is such that its basic vectors should have a very small component in the new dimensions \({\mathbb{R}}^ m\). This is solved by the author by giving the space \({\mathbb{R}}^{n+m}\) a different metric than usual. In fact, the distances in the extra dimensions are infinitesimally small in comparison to the distances in the original dimensions.
Reviewer: F.van der Linden

11-04 Software, source code, etc. for problems pertaining to number theory
11H06 Lattices and convex bodies (number-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
90C10 Integer programming
PDF BibTeX Cite
Full Text: DOI
[1] Buchmann, J.; Pethö, A., Computation of independent units in number fields by Dirichlet’s method, Math. comp., (1987), (in press) · Zbl 0597.12009
[2] Hastad, J.; Just, B.; Lagarias, J.C.; Schnorr, C.P., Polynomial time algorithms for finding integer relations among real numbers, Proceedings of STACS ’86, Lecture notes in computer science, (1986) · Zbl 0606.68033
[3] Lenstra, A.K.; Lenstra, H.W.; Lovasz, L., Factoring polynomials with rational coefficients, Math. ann., 26, 513-534, (1982) · Zbl 0488.12001
[4] Odlyzko, A., Cryptoanalytic attacks on the multiplicative knapsack cryptosystem and on Shamir’s fast signature system, IEEE trans. inform. theory, IT-30, 594-600, (1984) · Zbl 0548.94020
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.