Welcome to the resource topic for 2016/852
Title:
Faster LLL-type Reduction of Lattice Bases
Authors: Arnold Neumaier, 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.
ePrint: https://eprint.iacr.org/2016/852
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .