@inbook{9f503ebb51984fa7887d9fc4a25d1669,

title = "Floating-point LLL: theoretical and practical aspects",

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{\textquoteright}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.",

author = "Damien Stehl{\'e}",

year = "2009",

doi = "10.1007/978-3-642-02295-1_5",

language = "English",

isbn = "9783642022944",

series = "Information security and cryptography",

publisher = "Springer, Springer Nature",

pages = "179--213",

editor = "Nguyen, {Phong Q.} and Brigitte Vallee",

booktitle = "The LLL algorithm",

address = "United States",

}