### 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 language | English |
---|---|

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 |

Pages | 179-213 |

Number of pages | 35 |

ISBN (Print) | 9783642022944 |

DOIs | |

Publication status | Published - 2009 |

### Publication series

Name | Information security and cryptography |
---|---|

Publisher | Springer-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