Sébastien Balny (Doctorant GOC) présentera ses travaux le vendredi 13/12 à 10h30 en salle 301.
Another L makes it better? Lagrange meets LLL and may improve BKZ pre-processingRésumé :
We present a new variant of the LLL lattice reduction algorithm, inspired by Lagrange notion of pair-wise reduction, called L4. Similar to LLL, our algorithm is polynomial in the dimension of the input lattice, as well as in log M, where M is an upper-bound on the norm of the longest vector of the input basis.
We experimentally compared the norm of the first basis vector obtained with LLL and L4 up to dimension 200. On average we obtain vectors that are up to 16% shorter. We also used our algorithm as a pre-processing step for the BKZ lattice reduction algorithm with blocksize 24. In practice, up to dimension 140, this allows us to reduce the norm of the shortest basis vector on average by 3%, while the runtime does not significantly increases. In 10% of our tests, the whole process was even faster.
