Speeding-up lattice reduction with random projections (extended abstract)

Ali Akhavi, Damien Stehlé

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

3 Citations (Scopus)

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 factorization, cryptology, integer linear programming, etc. It can occur that the lattice to be reduced has a dimension which is small with respect to the dimension of the space in which it lies. This happens within LLL itself. We describe a randomized algorithm specifically designed for such rectangular matrices. It computes bases satisfying, with very high probability, properties similar to those returned by LLL. It 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, by using two different distributions of random matrices.
Original languageEnglish
Title of host publicationLATIN 2008
Subtitle of host publicationtheoretical informatics : 8th Latin American Symposium. Proceedings
EditorsEduardo Sany Laber, Claudson Bornstein, Loana Tito Nogueira, Luerbio Faria
Place of PublicationBerlin/Heidelberg, Germany
PublisherSpringer, Springer Nature
Pages293-305
Number of pages13
ISBN (Print)9783540787723
DOIs
Publication statusPublished - 2008
EventLatin American Symposium (8th : 2008) - Búzios, Brazil
Duration: 7 Apr 200811 Apr 2008

Publication series

NameLecture notes in computer science
PublisherSpringer
Volume4957
ISSN (Print)0302-9743

Conference

ConferenceLatin American Symposium (8th : 2008)
CityBúzios, Brazil
Period7/04/0811/04/08

Fingerprint Dive into the research topics of 'Speeding-up lattice reduction with random projections (extended abstract)'. Together they form a unique fingerprint.

Cite this