An LLL-reduction algorithm with quasi-linear time complexity
Andrew Novocin, Damien Stehlé and Gilles Villard
Abstract: We devise an algorithm, softL1, with the following
specifications: It takes as input an arbitrary basis B=(b_i)_i in Z^{d
x 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 O(d^{5+eps} beta + d^{omega+1+eps}
beta^{1+eps}) where beta = log max ||b_i|| (for any eps > 0 and omega
is a valid exponent for matrix multiplication). This is the first
LLL-reducing algorithm with a time complexity that is quasi-linear in
the bit-length beta of the entries and polynomial in the dimension
d. The backbone structure of softL1 is able to mimic the
Knuth-Schönhage fast gcd algorithm thanks to a combination of
cutting-edge ingredients. First the bit-size of our lattice bases can be
decreased via truncations whose validity are backed by recent
numerical stability results on the QR matrix factorization. Also we
establish a new framework for analyzing unimodular transformation
matrices which reduce shifts of reduced bases, this includes bit-size
control and new perturbation tools. We illustrate the power of this
framework by generating a family of reduction algorithms.
Download: pdf.
Homepage