multiplication de grands nombres

ARITHMETIQUE

Les algorithmes de multiplication classiques permettent d’effectuer des multiplications sur des nombres de quelques chiffres mais deviennent très longs à appliquer pour des grands nombres. Par exemple le produit de deux nombres de 4 chiffres nécessite 16 multiplications élémentaires et des additions. Dans de nombreuses situations des recherches contemporaines il deviendraient totalement impossible de réaliser les calculs nécessaires.
L’algorithme de Karatsuba (1962) réduit à 9 le nombre de multiplications élémentaires (pour un produit de deux nombres de 4 chiffres). L’algorithme de Toom-Cook (1963 et 1966) l’améliore en en donnant une généralisation.
L’algorithme de Schönhage-Strassen (1971) basé sur une transformée de Fourier a ensuite été le plus performant jusqu’en 2007 et la publication de l’algorithme de Fürer.
Il a été dépassé en 2019 par les résultats (encore théoriques) de David Harvey et Joris van der Hoeven.
Hoeven cite cet exemple : avec un temps d’exécution d’une multiplication élémentaire d’une nanoseconde, une multiplication de deux nombres d’un milliard de chiffres prendrait: (10⁹)² ns = 32 ans. L’algorithme connu de Schönhage-Strassen réduit ce temps à une trentaine de secondes sur un ordinateur ordinaire d’aujourd’hui. Avec le nouvel algorithme de 2019, la durée serait encore réduite.