GREYC

GREYC

Présentation du domaine des réseaux euclidiens

L'espace vectoriel $\mathbb {R}^n$ (appelé l'espace ambiant) étant muni de sa structure euclidienne classique, un réseau euclidien est l'ensemble des combinaisons linéaires entières d'un système libre de $p$ vecteurs 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. Réduire un réseau consiste à trouver parmi toutes ses bases, un représentant qui possède de bonnes propriétés vis à vis de la structure euclidienne: les vecteurs de la base doivent être assez courts et en même temps assez orthogonaux.

Parmi les notions de réductions possibles, celle introduite par Lovász en 82 a été la première à posséder un algorithme d'approximation polynomial permettant de construire la base réduite: l'algorithme LLL. Il dépend d'un paramètre d'approximation réel $t$. Cet algorithme a déjà de nombreuses applications : factorisation de polynômes à coefficients entiers, approximations diophantiennes, programmation linéaire entière, attaques intelligentes de différents cryptosystèmes, etc. Efficace et simple à implanter, l'algorithme LLL reste difficile à analyser tant pour la qualité de sa base de sortie que pour sa complexité. L'expérience montre que la borne donnée pour le nombre maximum de ses itérations est assez loin de la réalité. Lorsque l'on souhaite l'approximation optimale (le paramètre d'approximation est alors égal à $1$), même la complexité dans le pire des cas n'est pas connue.

Principaux résultats de la thèse

Le propos général de ma thèse est d'éclaircir le fonctionnement des différents processus de réduction des réseaux euclidiens et de suggérer de nouvelles stratégies algorithmiques en fonction des applications visées. Dans ce but, j'ai introduit de nouvelles réductions. L'idée consiste à affaiblir légèrement les conditions exigées par la réduction classique (LLL) afin d'obtenir des algorithmes plus rapides en moyenne qui obtiennent cependant des bases de qualité raisonnable. Puis, j'ai mené une étude comparative des différents algorithmes, en considérant leur nombre d'itérations et la qualité de leur base de sortie. Voici les principaux résultats.

2.1 Analyse dans le pire des cas des algorithmes de réduction.

En étudiant les défauts de longueur et d'orthogonalité des différentes bases de sortie, je montre que les nouvelles bases réduites, pourtant moins fines que les bases réduites au sens de Lovász, suffisent à la réalisation de la quasi-totalité des applications connues de la réduction des réseaux. En particulier, les premiers vecteurs de ces bases sont ``assez courts'' au même titre que ceux des bases LLL-réduites et c'est justement ce qu'exigent les applications. Par une analyse dans le pire des cas, j'exhibe la même borne pour la complexité de tous ces algorithmes (la borne qui existait déjà pour l'algorithme LLL). Cette première analyse montre que pour toutes les valeurs des paramètres d'approximation, exceptées les valeurs optimales, tous les algorithmes de réduction fonctionnent en temps polynomial par rapport à la taille et à la dimension de la base d'entrée.

L'originalité de mon analyse dans le pire des cas est dans l'étude de la complexité de l'algorithme LLL, pour la valeur optimale du paramètre d'approximation ($t=1$). Il s'agissait là d'un problème ouvert auquel j'ai apporté une réponse: l'algorithme LLL reste polynomial en la taille de la base d'entrée à dimension fixée. Dans ma thèse, je donne une borne explicite pour le nombre maximum d'itérations, linéaire en la taille de l'entrée en dimension $3$, ainsi qu'une caractérisation précise de la base de sortie. Plus récemment, j'ai montré que cette borne reste linéaire pour toute dimension fixée. Ces résultats ont fait l'objet d'un rapport de recherche au GREYC et d'un article accepté à la conférence internationale LATIN'2000 (Latin American Theoretical INformatics, Punta del Este, 10-14 avril 2000), et paru dans "Lecture Notes in Computer Science" 1776, pp 355-366.

2.2 Analyse probabiliste des algorithmes de réduction.

L'analyse dans le pire des cas ne sépare pas les différents algorithmes de réduction. C'est l'analyse en moyenne de ces algorithmes dans un modèle simple et naturel qui m'a permis de les classer. Je me place dans le modèle probabiliste où les vecteurs d'une base aléatoire sont choisis uniformément et indépendamment, dans la boule unité de $\mathbb {R}^n$. J'ai considéré ensuite les variables aléatoires correspondant aux rapports des normes de deux vecteurs différents de la base orthogonalisée (de Gram-Schmidt) associée à une base aléatoire.

(a) L'étude asymptotique de ces variables aléatoires, basée sur une généralisation de la méthode de Laplace, m'a permis de mettre en évidence des phénomènes de seuil surprenants. Cette étude m'a conduit d'une part à caractériser la qualité moyenne des bases aléatoires en fonction de leur ``poids'', paramètre exprimant le rapport de la dimension du réseau engendré par la base sur celle de l'espace ambiant. Par exemple, lorsque l'on choisit $k$ vecteurs dans une boule de dimension assez grande, ces vecteurs forment en moyenne une base presque orthogonale.

(b) D'autre part, dans le cadre du modèle probabiliste choisi, je montre que les bases réduites que j'ai introduites sont obtenues plus rapidement que les bases réduites au sens de LLL. Mieux, le nombre d'itérations des nouveaux algorithmes de réduction est alors asymptotiquement (en la dimension) le minimum possible. L'expérience confirme d'une part ces résultats de façon frappante (le régime asymptotique s'installe très vite). D'autre part, elle semble montrer que l'esprit de ces résultat reste valide dans d'autres modèles (provenant des applications).

Les nouveaux algorithmes de réduction et leur analyse en moyenne ont fait l'objet d'un article accepté au congrès ESA'99 (European Symposium of Algorithms), et paru dans "Lecture notes in computer science" 1643, pp 476-490. Un article long est soumis à "Theoretical Computer Science".