Floating-point LLL: theoretical and practical aspects
Damien Stehlé
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 bit-length
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-times and their
numerical behaviour. After 25 years of implementation, many questions
motivated by the practical side of LLL remain open.
Download: pdf.
Homepage