Cryptology ePrint Archive: Report 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.

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:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]