Faster LLL-type reduction of lattice bases
Arnold Neumaier and Damien Stehlé
Abstract: We describe an asymptotically fast variant of the LLL lattice
reduction algorithm. It takes as input a basis B in
Z^nxn and returns a (reduced) basis C of the Euclidean lattice
L spanned by B, whose first vector satisfies |c1| <=
(1 + c)(4/3)^((n-1)/4) (det L)^(1/n) for any fixed c > 0. It terminates
within O(n^(4+eps) beta^(1+eps)) bit operations for any eps > 0,
with beta = log max |bi|. It does rely on fast integer arithmetic
but does not make use of fast matrix multiplication.
Download: pdf.
Homepage