An LLL-Reduction Algorithm with Quasi-linear Time Complexity

We devise an algorithm, ˜ L 1, with the following specifications: It takes as input an arbitrary basis B =( b i) i ∈ Z d × d of a Euclidean lattice L ; It computes a basis of L which is reduced for a mild modification of the Lenstra-Lenstra-Lovász reduction; It terminates in time Õ ( d 5 × β) where β = log max || b i ||. This is the first LLL- reducing algorithm with a time complexity that is quasi-linear in the bit- length β of the entries and polynomial in the dimension d. This is joint work with Andrew Novocin and Gilles Villard.