A modification of the LLL reduction algorithm.

*(English)*Zbl 0629.10001This 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.

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

##### MSC:

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 |

##### Keywords:

computational number theory; reduction algorithm; modification of the Lenstra, Lenstra, Lovasz algorithm; lattice; LLL algorithm; basic vectors
Full Text:
DOI

##### References:

[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.