Paper 2016/852

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.