Algorithme de Fürer

Avant l'algorithme de Fürer, l'algorithme de Schönage-Strassen, datant de 1971, permettait de multiplier deux entiers en temps ${\displaystyle O(n\log n\log \log n)}$^[2]. Arnold Schönhage et Volker Strassen ont aussi conjecturé que la complexité minimale du produit rapide est ${\displaystyle O(n\log n)}$, où n est le nombre de bits utilisés dans l'écriture binaire des deux entiers en entrée.

L'algorithme de Fürer possède une complexité en ${\displaystyle O(n\log n\ 2^{O(\log ^{*}n)})}$, où ${\displaystyle \log ^{*}n}$ désigne le logarithme itéré. La différence entre les termes ${\displaystyle \log \log n}$ et ${\displaystyle 2^{\log ^{*}n}}$ est asymptotiquement à l'avantage de l'algorithme de Fürer mais le régime asymptotique n'est atteint que pour des très grands nombres^[3].

Un article écrit en 2014 par Harvey, van der Hoeven et Lecerf^[4] permet de montrer que l'algorithme de Fürer optimisé nécessite ${\displaystyle O(n\log n\ 16^{\log ^{*}n})}$ opérations et donne un algorithme qui ne nécessite que ${\displaystyle O(n\log n\ 8^{\log ^{*}n})}$ opérations, ainsi qu'un troisième algorithme en temps ${\displaystyle O(n\log n\ 4^{\log ^{*}n})}$ mais dont la validité repose sur une conjecture portant sur les nombres de Mersenne. Ces algorithmes sont parfois regroupés sous le terme d'algorithme de Harvey-van der Hoeven-Lecerf.

En 2019, Harvey et van der Hoeven atteignent une complexité algorithmique de ${\displaystyle O(n\log n)}$ pour la multiplication, battant la complexité de l'algorithme de Fürer. Le régime asymptotique est toutefois atteint pour des nombres d'une taille supérieure à ${\displaystyle 2^{1729^{12}}}$^[5].

• Arithmétique et théorie des nombres
• Portail de l'informatique théorique