Multiplier des nombres entiers encore plus rapidement

Depuis l’antiquité, les hommes ont cherché des méthodes efficaces pour multiplier des nombres de plus en plus grands. Certaines méthodes ont donné lieu à des appareils mécaniques comme les bouliers, ou la Pascaline que l’on peut admirer au Musée des arts et métiers à Paris. Avec l’essor de l’informatique, le problème de la multiplication a connu un regain d’intérêt. La découverte d’une méthode plus rapide que celle enseignée à l’école est due au mathématicien russe Anatoly Karatsuba en 1962. Elle a été le point de départ d’une série d’améliorations successives par Andrei Toom (1963), Stephen Cook (1966), Arnold Schönhage (1966), Donald Knuth (1969), Arnold Schönhage et Volker Strassen (1971), puis Martin Fürer (2007).

La multiplication des grands entiers est en effet un problème fondamental en informatique. Toute avancée sur ce problème implique des accélérations pour de nombreux autres algorithmes, au moins d’un point de vue théorique. Par exemple, de façon peu surprenante, la multiplication est cruciale pour le calcul rapide des décimales de $pi$ = 3,14159… Il s’agit d’un problème, certes plutôt ludique, qui est souvent utilisé comme vitrine par des constructeurs de superordinateurs, pour afficher la puissance de leurs machines. Depuis les années cinquante, les records sont régulièrement battus. Mais le fait qu’il soit aisé de calculer plusieurs milliards de chiffres de pi sur un ordinateur de bureau d’aujourd’hui est également le fruit de meilleurs algorithmes de calcul. En effet, les chercheurs conçoivent et programment des algorithmes qui repoussent constamment les limites offertes par la technologie.

Plus généralement, le produit des grands entiers est une des pierres angulaires des logiciels dits de calcul formel, qui sont utilisés pour toutes sortes de calculs mathématiques, à la fois dans les universités et l’industrie. Une autre application moins attendue intervient dans le cryptosystème RSA, qui est omniprésent dans des protocoles de sécurité informatique pour les cartes à puce et Internet. Chiffrer et déchiffrer des messages secrets demande en effet un grand nombre de multiplications de quelques centaines ou milliers de chiffres.

Les algorithmes modernes pour la multiplication rapide des entiers reposent tous sur une méthode appelée la transformée de Fourier rapide (FFT pour Fast Fourier Transform, en anglais). Une fonction peut être représentée soit par ses valeurs en certains points, soit par une formule mathématique, comme un polynôme en x. Ce passage d’une définition par coefficients à une définition par valeurs en certains points de la courbe s’appelle une interpolation. La transformée de Fourier permet de passer d’une représentation à l’autre et vice versa, et la FFT est un algorithme particulièrement rapide pour effectuer cette transformée.
Il est classique que pour effectuer un produit d’entiers, on en passe par une FFT qui permet de réduire la complexité du calcul. Un algorithme plus efficace pour la FFT donne alors automatiquement un meilleur algorithme de multiplication. L’innovation du nouvel algorithme de David Harvey1 , Joris van der Hoeven2 et Grégoire Lecerf2 repose sur l’utilisation habile d’une réduction dans l’autre sens, pour ramener des FFTs à des produits d’entiers. En effet, les chercheurs ont « coupé » les entiers en petits bouts, pour faciliter le calcul, et ont proposé une façon de recomposer les résultats qui permet de gagner en efficacité. Cette avancée fournit ainsi la meilleure méthode pour multiplier de grands entiers.

Plus techniquement, le résultat principal de ces chercheurs est une méthode pour multiplier deux entiers à $n$ chiffres en $c\,n \log n\,8^{\log^{\ast} n}$ secondes. Ici, $c$ est un nombre constant qui dépend seulement de la rapidité de l'ordinateur sur lequel on calcule. Pour des ordinateurs modernes, on a $c < 10^{- 10}$. La fonction log* est appelée "itérateur du logarithme" ; elle est définie par la récurrence $\log^{*} n = 0$ si $n \leq 1$ et $\log^{*} n = \log^{*} \log n + 1$ si $n > 1$. L'itérateur log* croît très lentement : par exemple $\log^{*} 10^{10^{10^{10}}} = 6$.

Peut-on faire encore mieux ? Les auteurs démontrent qu’il est plausible que « oui » : ils présentent aussi un algorithme qui nécessite seulement $c\,n \log n\, 4^{\log^{\ast} n}$ secondes pour faire une multiplication à $n$ chiffres, mais sous réserve qu’il existe « suffisamment » de nombres premiers de la forme $2^{p} - 1$, où $p$ est un autre nombre premier. Il s’agit des célèbres nombres premiers de Mersenne, comme $3=2^{2} - 1$, $7=2^{3} - 1$, $31=2^{5} - 1$, $8191=2^{13} - 1$, $131071=2^{17} - 1$, ou encore $2^{74207281} - 1$, qui est le plus grand nombre premier connu à ce jour. Pour chaque taille n, on conjecture qu’il existe un nombre premier de Mersenne dont le nombre de chiffres est du même ordre de grandeur que $n$. C’est expérimentalement ce qu’on observe, aussi loin que les ordinateurs le permettent.

Publication : David Harvey1 , Joris van der Hoeven2 , Grégoire Lecerf2 , Even faster integer multiplication, Journal of Complexity, 36:1–30, 2016. Prépublication