GREYC

GREYC

Résumé de la thèse

Mon travail est une étude algorithmique de la réduction des réseaux euclidiens. Un réseau euclidien est l'ensemble des combinaisons linéaires entières de $p$ vecteurs libres de $\mathbb {R}^n$. Les $p$ vecteurs forment alors une base du réseau et leur nombre est la dimension du réseau. Un même réseau peut ainsi être engendré par de multiples bases, qui peuvent être de qualité très variable. Réduire un réseau consiste à trouver une base qui engendre le même réseau et qui soit de bonne qualité vis-à-vis de la structure euclidienne: les vecteurs de la base doivent être assez courts et en même temps assez orthogonaux.

Le problème de la réduction est d'un interêt majeur en particulier par ses nombreuses applications en théorie algorithmique des nombres, en optimisation entière ou encore en cryptographie. En dimension $2$, il existe un algorithme de réduction dû à Gauss. En dimension $n$, le problème a intéressé des mathématiciens tels que Hermite et Minkowski, mais rarement de façon constructive. Ce n'est que depuis 1982 qu'il existe un algorithme d'approximation polynomial qui construit une base réduite (au sens de $t$-Lovász) dans un réseau: c'est le célèbre algorithme LLL baptisé des initiales de ses inventeurs, H.W. Lenstra, A.K. Lenstra et L. Lovász, qui sert à la fois de point de départ et de référence constante à ma thèse.

Dans ma thèse, je considère plusieurs nouvelles définitions de bases réduites et je compare ces réductions à celle de $t$-Lovász. Les nouvelles réductions sont a priori moins fortes. Mais la qualité des bases de sortie reste similaire à celle des bases LLL-réduites, alors que les nouveaux algorithmes de réduction sont en moyenne plus rapides.

Les nouveaux algorithmes de réduction sont définis dans le Chapitre $2$, où je fournis également une analyse dans le pire des cas et une étude comparative des bases de sortie.

Les Chapitres $3$-$6$ étudient le comportement des différents algorithmes de réduction sur des réseaux aléatoires. Mes résultats sont basés d'une part sur un théorème de Daudé et Vallée sur la longueur des orthogonalisés d'une base aléatoire et d'autre part sur une généralisation de la méthode de Laplace que je propose dans le Chapitre $4$. Ainsi, je mets en évidence des phénomènes de seuil dans les réseaux aléatoires qui me permettent ensuite de classer les algorithmes de réduction (l'analyse dans le pire des cas n'arrivait pas à les distinguer).

En analysant les agorithmes de réduction dans le pire des cas et en moyenne sur les bases du modèle uniforme, je fournis une étude comparative de leurs comportements et je montre que les nouveaux algorithmes sont plus rapides. Mon analyse est complétée (Chapitre $8$) par des exprérimentations qui confirment mes résultats sur des réseaux aléatoires provenant de problèmes réels.

Dans le Chapitre $7$, je considère la complexité de l'algorithme LLL, lorsque son paramètre d'approximation $t$ prend sa valeur optimale $1$ (la meilleure base réduite est alors construite). C'était un problème ouvert auquel j'ai apporté une réponse: l'algorithme LLL optimal reste polynomiale en la taille de la base lorsque la dimension $n$ du réseau ext fixé.

Mots-clefs : algorithmique, complexité, analyse en moyenne, réseaux euclidiens, bases réduites, algorithme LLL, calcul formel, cryptographie, réseaux aléatoires, distribution uniforme, probabilités asymptotiques, lois 0-1.