Floating-point LLL

theoretical and practical aspects

Damien Stehlé

Research output: Chapter in Book/Report/Conference proceedingChapter

9 Citations (Scopus)

Abstract

The text-book LLL algorithm can be sped up considerably by replacing the underlying rational arithmetic used for the Gram–Schmidt orthogonalisation by floating-point approximations. We review how this modification has been and is currently implemented, both in theory and in practice. Using floating-point approximations seems to be natural for LLL even from the theoretical point of view: it is the key to reach a bit-complexity which is quadratic with respect to the bitlength of the input vectors entries, without fast integer multiplication. The latter bit-complexity strengthens the connection between LLL and Euclid’s gcd algorithm. On the practical side, the LLL implementer may weaken the provable variants in order to further improve their efficiency: we emphasise on these techniques. We also consider the practical behaviour of the floating-point LLL algorithms, in particular their output distribution, their running-time and their numerical behaviour. After 25 years of implementation, many questions motivated by the practical side of LLL remain open.
Original languageEnglish
Title of host publicationThe LLL algorithm
Subtitle of host publicationsurvey and applications
EditorsPhong Q. Nguyen, Brigitte Vallee
Place of PublicationHeidelberg ; New York
PublisherSpringer, Springer Nature
Pages179-213
Number of pages35
ISBN (Print)9783642022944
DOIs
Publication statusPublished - 2009

Publication series

NameInformation security and cryptography
PublisherSpringer-Verlag

Fingerprint Dive into the research topics of 'Floating-point LLL: theoretical and practical aspects'. Together they form a unique fingerprint.

  • Cite this

    Stehlé, D. (2009). Floating-point LLL: theoretical and practical aspects. In P. Q. Nguyen, & B. Vallee (Eds.), The LLL algorithm: survey and applications (pp. 179-213). (Information security and cryptography). Heidelberg ; New York: Springer, Springer Nature. https://doi.org/10.1007/978-3-642-02295-1_5