Speeding-up Lattice Reduction with Random Projections (Extended Abstract)

Ali Akhavi and Damien Stehlé

Abstract: Lattice reduction algorithms such as LLL and its floating-point variants have a very wide range of applications in computational mathematics and in computer science: polynomial factorisation, cryptology, integer linear programming, etc. It can occur that the lattices to be reduced have a dimension which is small with respect to the dimension of the space in which it lies. This happens within the LLL algorithm itself. We describe a randomised algorithm specifically designed for such rectaangular matrices. It computes bases satisfying, with very high probability, properties similar to those returned by LLL. The algorithm significantly decreases the complexity dependence in the dimension of the embedding space. Our technique mainly consists in randomly projecting the lattice on a lower dimensional space. To achieve the result, we strengthen a tool that may be of independent interest: we analyze the orthogonalisation of some type of random matrices, the so-called random ball sampling.

Download: pdf.

Corresponding Magma code, under GPL-v2: here, with the corresponding matrix.