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.