A modification of the LLL reduction algorithm (Q1093661)

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.