Sommaire

  • Cet exposé a été présenté le 13 mai 2011.

Description

  • Orateur

    Andy Novocin - ENS Lyon

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.<br/> To achieve this we present an independently interesting toolkit for analyzing incremental lattice reductions.

Prochains exposés

Voir les exposés passés