Ali Akhavi, Laboratoire GREYC, Université de Caen

Phénomènes de seuil dans les réseaux aléatoires et analyse en moyenne d'algorithmes de réduction

Le problème de la réduction des réseaux euclidiens est d'un intérêt majeur en particulier par ses nombreuses applications en théorie algorithmique des nombres, en optimisation entière ou encore en cryptographie Je présenterai deux nouveaux algorithmes de réduction, appelés réduction de Gram et réduction de Schmidt, qui sont obtenus en relaxant les conditions exigées par l'algorithme classique de réduction : LLL. L'analyse dans le pire des cas de ces différents algorithmes ne permet pas de les différencier. Je me placerai alors dans un modèle aléatoire simple et naturel, où les vecteurs d'entrée sont choisis uniformément et indépendamment dans la boule unité. L'étude de la géométrie des réseaux aléatoires mettra en évidence des phénomènes de seuils et permettra de montrer que les nouveaux algorithmes introduits sont en moyenne plus efficaces que l'algorithme classique : Les bases de sortie sont de qualité similaire et obtenues bien plus rapidement en moyenne.