Symbolic Computation Group

Friday, November 4, 2011 at 1:30pm, at U. of Western Ontario

Abstract:

The LLL lattice reduction algorithm of 1982 has proven to be useful in a wide variety of fields. It can be used to approximately solve computationally difficult lattice-based problems, such as the shortest vector problem, in polynomial time. We present a new algorithm for lattice reduction which is the first algorithm to have a complexity bound which is both polynomial and quasi-linear in the bit-length of the input. To achieve this we present an independently interesting toolkit for analyzing incremental lattice reductions.