Algorithme de Fürer

L'algorithme de Fürer est un algorithme de multiplication de très grands entiers. Il a été publié en 2007 par le mathématicien suisse Martin Fürer de l'université d'État de Pennsylvanie. Cet algorithme possède asymptotiquement une des plus faibles complexités parmi les algorithmes de multiplication et est donc meilleur que l'algorithme de Schönhage-Strassen. Son régime asymptotique n'est atteint que pour de très grands entiers.

Histoire

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

Complexité

L'algorithme de Fürer possède une complexité en $O(n\log n\ 2^{O(\log ^{*}n)})$, où $\log ^{*}n$ désigne le logarithme itéré. La différence entre les termes $\log \log n$ et $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.

Un article écrit en 2014 par Harvey, van der Hoeven et Lecerf permet de montrer que l'algorithme de Fürer optimisé nécessite $O(n\log n\ 16^{\log ^{*}n})$ opérations et donne un algorithme qui ne nécessite que $O(n\log n\ 8^{\log ^{*}n})$ opérations, ainsi qu'un troisième algorithme en temps $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 $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 à $2^{1729^{12}}$.