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