| Andy Novocin |  |
 |
Date de l'exposé : 13 mai 2011
L1 a new quasi-linear LLL algorithm
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 bound in the bit-length of the input. To achieve this we present an independently interesting toolkit for analyzing incremental lattice reductions.
