CCIS Seminar - Tuesday 31 March 2009 - CTL
15:30:00 - Salle de CTL

Guillaume Hanrot, LORIA Equipe CACAO

Problèmes d'énumération dans les réseaux.

Résumé : Un reseau euclidien est un sous-groupe discret de \R^n, ou encore un "quadrillage regulier" dans R^n. En cryptographie mais aussi dans d'autres contextes (eg. codes correcteurs), etant donne un reseau, on est souvent amene a resoudre ou approcher les problemes suivants : Trouver un vecteur non nul le plus court du reseau ; Etant donne x \in \R^n, trouver un vecteur non nul du reseau le plus proche de x. Ces deux problemes sont calculatoirement difficiles. La meilleure methode connue pour les resoudre est probabiliste, et exponentielle en temps et en espace. La meilleure methode deterministe, due a Kannan, est fondee sur une strategie d'enumeration, qui suit un long precalcul destine a calculer une base "tres reduite" du reseau. Nous presenterons une analyse detaillee de la strategie d'enumeration, montrant en particulier que la complexite de la recherche du vecteur le plus court est exactement $d^{d/(2e)(1+o(1))} \poly(n)$ (ou $d$ est le cardinal d'une base du reseau), et donnerons un encadrement de la complexite optimale pour le probleme du vecteur le plus proche.


Home page CCIS Seminars
How to come to CTL - http://www-verimag.imag.fr/Plan-d-acces.html?lang=fr