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.
|Title of host publication||The LLL algorithm|
|Subtitle of host publication||survey and applications|
|Editors||Phong Q. Nguyen, Brigitte Vallee|
|Place of Publication||Heidelberg ; New York|
|Publisher||Springer, Springer Nature|
|Number of pages||35|
|Publication status||Published - 2009|
|Name||Information security and cryptography|