Symbolic Computation Group

David R. Cheriton School of Computer Science
University of Waterloo, Waterloo, Ontario, Canada

L1, a quasi-linear LLL algorithm
Andy Novocin, University of Waterloo
Friday, November 4, 2011 at 1:30pm, at U. of Western Ontario


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.


Last modified on Sunday, 04 November 2012, at 15:42 hours.