Complexité de la multiplication

Poser une multiplication de deux entiers de n chiffres selon la méthode babylonienne classique requiert n^2 (n au carré) multiplications élémentaires. En 1971 Schönhage et Strassen (aussi connu pour la multiplication rapide des matrices) en ont donné un algorithme plus rapide. Plus récemment, au mois de mars Joris van der Hoeven ( CNRS  École Polytechnique Computer Science Laboratory LIX) et David Harvey (University of New South Wales (Australia)) ont trouvé un algorithme qui effectue le produit d’entiers de taille n avec une complexité en O(n log n).

Leur travail est disponible ici :
https://hal.archives-ouvertes.fr/hal-02070778