AG Diskrete Mathematik und Mathematische Informatik

AG Diskrete Mathematik und Mathematische Informatik
Winter Term 2007 / 2008

Prof. Dr. C.-P. Schnorr, Prof. Dr. T. Theobald
Dr. H. Bosse, R. Hartung, C. Riener, A. Scemama, R. Steffens

Speeding up Lattice Reduction with Random Projections

Lecture by Ali Akhavi, Univ. Caen,
08. Feb. 08, 14 ct, Raum 612

Abtract:

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.

AG Home