Paper 2016/852
Faster LLLtype 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)^{(n1)/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.
Metadata
 Available format(s)
 Publication info
 Published elsewhere. ISSAC 2016
 Contact author(s)
 damien stehle @ gmail com
 History
 20160907: received
 Short URL
 https://ia.cr/2016/852
 License

CC BY
BibTeX
@misc{cryptoeprint:2016/852, author = {Arnold Neumaier and Damien Stehle}, title = {Faster LLLtype Reduction of Lattice Bases}, howpublished = {Cryptology ePrint Archive, Paper 2016/852}, year = {2016}, note = {\url{https://eprint.iacr.org/2016/852}}, url = {https://eprint.iacr.org/2016/852} }