**Faster LLL-type Reduction of Lattice Bases**

*Arnold Neumaier and Damien Stehle*

**Abstract: **We describe an asymptotically fast variant of the LLL lattice reduction algorithm. It takes as input a basis $\mathbf B \in \mathbb Z^{n \times n}$ and returns a (reduced) basis $\mathbf C$ of the Euclidean lattice $L$ spanned by $\mathbf B$, whose first vector satisfies $||\mathbf c_1|| \leq (1+c)(4/3)^{(n-1)/4} \cdot (\det L)^{1/n}$ for any fixed $c>0$. It terminates within $O(n^{4+\epsilon} \beta^{1+\epsilon})$ bit operations for any $\epsilon >0$, with $\beta = \log \max_i ||\mathbf b_i||$. It does rely on fast integer arithmetic but does not make use of fast matrix multiplication.

**Category / Keywords: **

**Original Publication**** (in the same form): **ISSAC 2016

**Date: **received 4 Sep 2016, last revised 7 Sep 2016

**Contact author: **damien stehle at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20160907:142425 (All versions of this report)

**Short URL: **ia.cr/2016/852

[ Cryptology ePrint archive ]