Analyse fine de l’algorithme d’Euclide
Loïck Lhôte (GREYC)L’algorithme d’Euclide est souvent considéré comme le plus vieil algorithme au monde et il reste aujourd’hui (avec ses variantes) un des algorithmes de base pour de nombreuses applications: simplifications de calculs, cryptographie à clés publiques, tests de primalité, factorisation de polynômes,…. Jebelean a montré que pour certains problèmes arithmétiques, les calculs de PGCD représentent 60% du temps total d’exécution et ce chiffre monte à 80% pour le calcul de bases de Gröbner. Comprendre et analyser l’algorithme d’Euclide est donc essentiel.
Les analyses (probabilistes) de l’algorithme d’Euclide ont commencé dans les années 1970 avec Heilbronn et Dixon et jusqu’à il y a dix ans, seul un paramètre (le nombre d’étapes) avait été étudié. Depuis une dizaine d’années, le groupe de Caen autour de Brigitte Vallée a développé une approche générale, l’analyse dynamique, qui s’applique à toute une classe d’algorithmes du pgcd ainsi qu’à de nombreux paramètres comme le nombre d’étapes, la taille binaire de tous les quotients, la complexité binaire (ou en bits), la taille des continuants, …. Au départ, les analyses dynamiques se limitaient à des analyses en moyenne (ou de l’espérance) mais en 2002, Viviane Baladi et Brigitte Vallée ont effectué une percée significative: elles ont adapté l’analyse dynamique pour réaliser la première analyse fine (i.e. en distribution) de toute une classe de paramètres dits additifs et à croissance modérée. Pour faire un comparatif avec les notes d’une classe, l’analyse en moyenne correspond au calcul de la moyenne de la classe alors que l’analyse en distribution détermine la probabilité qu’une note soit dans une fourchette donnée. C’est donc une analyse beaucoup plus précise mais aussi plus difficile.
La classe des co=FBts additifs et à croissance modérée est vaste et contient par exemple le nombre d’étapes ou la taille binaire de tous les quotients. Mais ni la complexité binaire, ni la taille des continuants ne sont additifs alors que le premier paramètre est celui qui décrit le mieux la vitesse de l’algorithme et que le second est fondamental dans l’analyse des algorithmes récursifs.
Au cours de cet exposé, je présenterai l’analyse fine de plusieurs paramètres dont la complexité binaire des algorithmes d’Euclide classique [qui calcule le pgcd] et étendu [qui calcule en plus les coefficients de Bezout], lorsque les entrées sont des entiers ou des polynômes. Les analyses dans le cas des polynômes sont simples et font appel aux techniques classiques de combinatoire analytique. L’analyse dans le cas des entiers est plus évoluée et nous utiliserons les méthodes d’analyse dynamique mises au point par Baladi et Vallée. Je mettrai en évidence les similarités et les différences entre le cas des polynômes et des entiers et si le temps me le permet, j’aborderai l’analyse fine des continuants.