Algorithmes quasi-optimaux : aussitôt dit, aussitôt fait

On apprend à l'école comment ajouter ou multiplier deux entiers. La division euclidienne et son application au calcul du PGCD viennent ensuite, et, plus tard, la multiplication des polynômes, puis des matrices. Pour chacun de ces problèmes, la méthode apprise à l'école est la plus facile à expliquer et la plus commode lorsque l'on traite des données de petite taille. Mais, d'un point de vue asymptotique, la méthode naïve n'est pas la meilleure, sauf pour l'addition. Pour multiplier deux nombres entiers, par exemple, il existe des algorithmes quasi-optimaux, c'est-à-dire des méthodes de calcul qui ne demandent pas (beaucoup) plus de temps qu'il n'en faut pour écrire le résultat. On ne peut donc espérer de meilleurs algorithmes. Ces méthodes de multiplication rapide utilisent la transformée de Fourier discrète. Inventées dans les années 1970, elles se sont répandues grâce à la micro-informatique et aux logiciels de calcul formel. Quant à la multiplication des matrices, Strassen et d'autres ont proposé depuis 1969 des méthodes théoriquement plus rapides que la méthode standard; mais on ignore s'il existe des algorithmes optimaux: multiplier deux matrices est aujourd'hui bien plus lent que de recopier le résultat. Majorer le rang du tenseur de multiplication des matrices est une question importante et difficile. Cohn et Umans on récemment reformulé cette question en termes de combinatoire et de représentations de groupes finis.

Dans la première partie de mon exposé je présenterai quelques uns de ces problèmes importants de complexité algébrique.

Je présenterai ensuite un travail commun avec Reynald Lercier, qui donne un algorithme quasi-optimal pour produire des polynômes irréductibles sur un corps fini, à l'aide de la théorie de Kummer des courbes elliptiques. La même question pour les entiers premiers reste ouverte.