Amélioration de l'analyse de l'algorithme de Kannan pour résoudre SVP

Le problème du vecteur le plus court d'un réseau euclidien est NP-difficile sous des réductions randomisées. Plusieurs cryptosystèmes reposent sur des variantes affaiblies de ce problème. Pour cette raison, il est important de connaître précisément la complexité des algorithmes qui le résolvent. Le plus classique d'entre eux, et le seul à être pratique, est l'algorithme de Kannan. Nous améliorons sa meilleure borne de complexité connue et généralisons notre analyse à d'autres problèmes difficiles sur les réseaux euclidiens.

Travail en commun avec Guillaume Hanrot.