Soutenance mémoire
L’analyse d’algorithmes. C’est une branche de l’informatique mathématique fondée par Don Knuth dans les années 60, qui étudie mathématiquement le comportement des algorithmes, non pas dans le pire des cas comme c’est l’habitude, mais plutôt sur des instances “génériques”. Ces analyses permettent de prédire le comportement “pratique” des algorithmes, mais aussi, et c’est souvent le plus important, de mieux comprendre leur structure, et d’isoler les noeuds de difficulté algorithmique. C’est donc aussi un puissant moteur d’amélioration algorithmique. L’ouvrage fondateur du sujet est l’ensemble des trois livres qui forment The Art of Computer Programming [35, 36, 37], tous parus entre la fin des années 60 et le début des années 70. Depuis, toute une communauté s’est créée sur cette thématique, et le livre de Flajolet et Sedgewick, [23] tout récemment publié, peut être considéré comme l’ouvrage qui fonde le domaine de la combinatoire analytique, qui est historiquement l’outil mathématique principal de l’analyse d’algorithmes jusqu’à l’heure actuelle.
La combinatoire analytique traite les problèmes combinatoires en utilisant l’objet central des séries génératrices, en utilisant des méthodes à la fois formelles et analytiques. La série génératrice est d’abord considérée comme une série formelle. Sa structure permet alors de refléter la combinatoire du problème et ce sont ses coefficients, via leur analyse asymptotique, qui vont permettre de revenir au problème de départ. Le comportement asymptotique de ces coefficients va dépendre fortement des singularités de la série génératrice, désormais vue comme une fonction de variable complexe.
Algorithmique des réseaux euclidiens
Les réseaux euclidiens
La géométrie des nombres est une branche de la théorie de nombres introduite par Hermann Minkowski en 1896 [57]. Sa motivation première est l’étude des formes quadratiques définies sur Zn , et elle adopte un point de vue géométrique. Lorqu’on effectue un changement de base, la base canonique de Zn se transforme en une base de Rn , et l’ensemble Zn en l’lensemble des combinaisons linéaires entières de vecteurs de cette base, ce qu’on appelle un réseau euclidien, tandis que les formes quadratiques définies positives se relient à la norme euclidienne. Le minimum de la norme euclidienne, appelé premier minimum, est alors la longueur d’un vecteur le plus court non nul du réseau. Il joue un rôle central dans le domaine. Ces objets mathématiques que sont les réseaux se révèlent être un outil de modélisation incontournable. Beaucoup de problèmes, de nature a priori très diverse, comme l’approximation diophantienne simultanée, la factorisation de polynômes, la factorisation d’entiers, la programmation linéaire entière, et, plus récemment des systèmes cryptographiques, s’expriment dans le vocabulaire des réseaux ; Leur résolution se ramène à des questions de base sur un réseau, et très souvent, à la détermination du premier minimum du réseau. C’est parce que la modélisation via les réseaux est à la fois universelle et puissante que les problèmes de base des réseaux deviennent eux aussi essentiels à résoudre.
Réseaux euclidiens
Il s’agit d’abord de décrire les principaux objets reliés à une base. On définit ensuite un réseau euclidien, et les pricipaux paramètres qui décrivent sa géométrie (minima successifs, déterminant, défaut d’Hermite) reliés par le théorème de Minkowski.
Orthogonalisée de Gram-Schmidt, Matrice de Gram, Parallélotope fondamental
L’espace vectoriel réel Rn , n ≥ 1 est muni de sa structure euclidienne et de la mesure de Lebesgue, notée µ. La base canonique de Rn est désignée par (e1, e2, .. . ,en). Le produit scalaire de v, u ∈ Rn , et la norme euclidienne de u sont respectivement désignés par v·u, et ||u|| = (u·u) 1/2 . A une partie E ⊆ Rn , nous associons l’espace vectoriel réel engendré par E, que nous désignons par hEi.
L’ensemble des matrices à n ≥ 1 lignes et m ≥ 1 colonnes, avec des coefficients dans un ensemble S (en pratique R,Q ou Z) est noté Sⁿˣᵐ. Pour une matrice M, nous désignons sa transposée par tM, son déterminant par det M et sa matrice inverse, (quand elle existe) par M−1 .
Forme normale d’Hermite
Puisqu’un réseau admet une infinité de bases, qui n’ont pas du tout la même forme, il peut être utile, pour comparer les réseaux entre eux, par exemple, de déterminer une forme normale pour les bases possibles de ces réseaux. La forme normale la plus employée est la forme normale d’Hermite, que nous décrivons maintenant dans le cas où les réseaux sont de dimension pleine n = p.
Définition. Une base B := (bi,j ) ∈ Rⁿˣⁿ d’un réseau de dimension n dans Rⁿ est sous forme normale d’Hermite lorsqu’elle s’exprime sous forme triangulaire dans la base canonique de Rn . Plus précisément,
(i) B est triangulaire inférieure
(ii) Les éléments de la diagonale bi,i sont tous strictement positifs.
(iii) Pour tout j < i, on a les inégalités suivantes : 0 ≤ bi,j < bi,i.
Proposition . Tout réseau L de Rn de dimension pleine admet une unique base sous forme normale d’Hermite.
La forme normale d’Hermite permet donc de représenter un réseau de manière canonique, dans un sens “algébrique”. En revanche, il n’est pas du tout clair (et de fait c’est rarement le cas) qu’une telle base possède des propriétés euclidiennes intéressantes.
Problèmes algorithmiques de base
Dans cette section, nous présentons les problèmes algorithmiques qui se posent naturellement dans l’étude des réseaux, quand ils sont considérés “pour eux-mêmes”, indépendamment de leurs applications potentielles. Ces problèmes admettent des énoncés de nature diverse : ensembliste, algébrique, ou euclidien.
Représentation des réseaux
La plupart des problèmes étudiés dans ce chapitre ont un sens quand les réseaux sont des réseaux quelconques de Rn . Les algorithmes qui les résolvent sont aussi le plus souvent bien définis sur des réseaux quelconques de Rn , à condition de définir un modèle de calcul sur les nombres réels. Mais, si on veut faire de l’algorithmique et étudier la complexité de ces problèmes, il faut considérer une notion de taille d’entrée. Un réseau est donné le plus souvent par une base, parfois seulement par un système générateur, formé d’éléments de Qn , qu’on peut toujours ramener dans Zn en multipliant tous les rationnels par le ppcm de leurs dénominateurs. On peut alors définir une notion de taille d’entrée. La taille d’un tel système B = (b1, .. . ,bp) de p vecteurs de Zn est choisie comme étant
τ (B) = Θ(pn) · log M où M = max {bi,j ; i ∈ (1, p), j ∈ (1, n)}. (1.4)
|
Table des matières
Introduction
Chapitre 1 Les réseaux euclidiens
1.1 Réseaux euclidiens
1.1.1 Orthogonalisée de Gram-Schmidt, Matrice de Gram, Parallélotope fondamental
1.1.2 Réseaux
1.1.3 Minima successifs
1.1.4 Théorème de Minkowski
1.1.5 Défaut d’Hermite et constante d’Hermite
1.1.6 Forme normale d’Hermite
1.2 Problèmes algorithmiques de base
1.2.1 Représentation des réseaux
1.2.2 Problèmes ensemblistes
1.2.3 Problèmes algébriques
1.2.4 Problèmes euclidiens
1.2.5 Les algorithmes de résolution pour les problèmes ensemblistes ou algébriques
1.2.6 La difficulté des problèmes euclidiens
1.2.7 Le problème de la réduction
1.2.8 Stratégie générale de la résolution des problèmes
1.3 Problèmes algorithmiques résolus via les réseaux
1.3.1 Factorisation de polynômes (1)
1.3.2 Factorisation de polynômes (2)
1.3.3 Approximations diophantiennes simultanées
1.3.4 Cryptanalyse des systèmes cryptographiques fondés sur le sac-à-dos
1.3.5 Prédictibilité de la suite de bits produits par le générateur congruentiel linéaire
1.3.6 Calcul de racines k-ièmes modulo n
1.3.7 Méthode de Coppersmith
1.3.8 Cryptosystème NTRU
Chapitre 2 La réduction des réseaux
2.1 Algorithmes de réduction en dimension 1
2.1.1 L’algorithme d’Euclide
2.1.2 Divisions euclidiennes centrées
2.1.3 Algorithmes d’Euclide centrés
2.1.4 Algorithme des fractions continues centrées
2.1.5 Une première analyse des algorithmes d’Euclide centrés
2.2 Algorithmes de réduction en dimension 2
2.2.1 Bases minimales
2.2.2 Bases positives et aigues
2.2.3 Algorithmes de Gauss : les deux versions Gauss-positif et Gauss-aigu
2.2.4 Comparaison entre les deux algorithmes
2.2.5 Nombre d’itérations de l’algorithme de Gauss. Une première borne
2.2.6 Paramètres liés à l’exécution de l’algorithme
2.2.7 Paramètres liés à la configuration de sortie
2.3 Algorithmes de réduction en dimension n quelconque
2.3.1 Réduction en taille : l’algorithme Propre
2.3.2 Réduction au sens de Lovász
2.3.3 Description de l’algorithme LLL(t)
2.3.4 Effet des échanges de l’algorithme
2.3.5 Paramètres d’exécution
2.3.6 Une variante de l’algorithme LLL : l’algorithme Pair-Impair
Chapitre 3 Premiers résultats sur le comportement probabiliste de l’algorithme LLL
3.1 Analyse probabiliste d’un algorithme. L’exemple des algorithmes de réduction
3.1.1 Analyse probabiliste d’un algorithme
3.1.2 L’exemple de l’algorithme d’Euclide
3.1.3 L’exemple de l’algorithme de Gauss
3.1.4 L’exemple de l’algorithme LLL
3.2 Modèles aléatoires d’entrées pour les algorithmes de réduction
3.2.1 Modèles sphériques
3.2.2 Notion naturelle de réseau aléatoire
3.2.3 Les bases d’Ajtai
3.2.4 Réseaux des applications : Variantes des bases sac-à-dos et de ses transposées
3.2.5 Modèles probabilistes continus ou discrets
3.3 Analyses existantes dans les modèles sphériques
3.3.1 Intégrales eulériennes : fonctions gamma et beta
3.3.2 Principaux paramètres
3.3.3 Probabilité qu’une base d’entrée soit déjà réduite
3.3.4 Lois β pour les rapports de Siegel
3.3.5 Le processus limite
3.3.6 Une première analyse probabiliste de l’algorithme LLL
3.3.7 Lois puissances pour les rapports de Siegel de la fin
3.4 Résultats expérimentaux et conjectures sur le comportement probabiliste de l’algorithme
3.4.1 Géométrie de la sortie
3.4.2 Paramètres d’exécution
3.4.3 Le travail de cette thèse
Conclusion
