Introduction
La multiplication de Schönhage-Strassen est un algorithme de multiplication rapide de très grands entiers publié en 1971 par les mathématiciens allemands Arnold Schönhage et Volker Strassen. Il représente l'une des plus importantes avancées de l'histoire de l'algorithmique, puisqu'il a été, pendant près de quarante ans, l'algorithme le plus rapide connu pour la multiplication de très grands nombres. Son apparition a profondément transformé les domaines du calcul scientifique, de la théorie des nombres et de la cryptographie, où la manipulation d'entiers comportant des centaines de milliers ou des millions de chiffres est fréquente.
Contrairement aux méthodes classiques, qui effectuent directement des multiplications entre les chiffres composant les opérandes, l'algorithme de Schönhage-Strassen transforme le problème en une multiplication de polynômes. Cette opération est ensuite accélérée grâce à une variante de la Transformée de Fourier Rapide (FFT) adaptée à l'arithmétique des entiers. Cette approche réduit considérablement le nombre d'opérations nécessaires lorsque la taille des nombres devient très importante. Pour les entiers de petite taille, la méthode classique, Karatsuba ou Toom-Cook demeurent généralement plus efficaces, mais à partir de plusieurs milliers de chiffres, Schönhage-Strassen devient nettement plus performant.
Historique
Avant les années 1960, la multiplication classique constituait pratiquement la seule méthode utilisée pour multiplier des nombres entiers. En 1960, Anatoli Karatsuba démontra qu'il était possible de faire mieux que la complexité quadratique. Quelques années plus tard, Andreï Toom et Stephen Cook généralisèrent cette idée avec l'algorithme de Toom-Cook.
En 1971, Arnold Schönhage et Volker Strassen publièrent un nouvel algorithme utilisant des techniques totalement différentes. Plutôt que d'améliorer progressivement les multiplications classiques, ils exploitèrent les propriétés de la transformée de Fourier afin de convertir une multiplication difficile en une suite d'opérations beaucoup plus simples.
Pendant plusieurs décennies, cet algorithme fut considéré comme la référence absolue pour la multiplication des très grands entiers. Ce n'est qu'en 2007, avec les travaux de Martin Fürer, puis en 2019, avec ceux de David Harvey et Joris van der Hoeven, que sa complexité théorique fut dépassée.
Principe
Le principe général consiste à représenter les deux grands nombres comme des polynômes.
Par exemple, un entier peut être découpé en plusieurs blocs :
| 123456789012 |
devient :
| [123] [456] [789] [012] |
Chaque bloc est considéré comme le coefficient d'un polynôme.
La multiplication de deux grands entiers revient alors à multiplier deux polynômes.
Une multiplication classique de polynômes nécessite un très grand nombre d'opérations. Schönhage-Strassen accélère ce calcul grâce à une Transformée de Fourier Rapide adaptée aux calculs entiers.
Le principe général est le suivant :
- Découper les deux nombres.
- Construire les polynômes.
- Appliquer une transformée rapide.
- Multiplier les coefficients obtenus.
- Effectuer une transformée inverse.
- Reconstruire le nombre final.
Cette méthode permet d'éviter un très grand nombre de multiplications coûteuses.
La Transformée de Fourier discrète
Dans les applications classiques de traitement du signal, la Transformée de Fourier Discrète (DFT) utilise des nombres complexes.
Schönhage-Strassen adopte une approche différente.
Au lieu de travailler directement avec les nombres complexes, l'algorithme effectue les calculs dans des anneaux modulaires, c'est-à-dire des ensembles d'entiers où les opérations sont réalisées modulo une certaine valeur.
Cette approche présente plusieurs avantages :
- elle évite les erreurs d'arrondi liées aux nombres réels ;
- elle garantit des résultats exacts ;
- elle permet des calculs extrêmement rapides sur les grands entiers.
Cette adaptation constitue l'une des principales innovations de l'algorithme.
Algorithme simplifié
Le fonctionnement général peut être résumé ainsi :
|
MODULE SchonhageStrassen(A,B) Découper les deux nombres Construire deux polynômes Appliquer la FFT modulaire Multiplier chaque coefficient Calculer la transformée inverse Propager les retenues Reconstruire le résultat RETOURNER le produit |
En pratique, chaque étape est elle-même composée de nombreux traitements récursifs et d'optimisations mathématiques.
Exemple conceptuel
Considérons les deux nombres :
|
123456 654321 |
Ils sont découpés en blocs :
|
[123] [456] [654] [321] |
Les blocs deviennent les coefficients de deux polynômes.
Après application de la transformée rapide :
- les coefficients sont multipliés terme à terme ;
- la transformée inverse est calculée ;
- les retenues sont propagées.
Le résultat final est exactement identique à celui obtenu avec une multiplication classique, mais beaucoup plus rapidement lorsque les nombres deviennent très grands.
Complexité
Les principales méthodes de multiplication peuvent être comparées ainsi :
| Algorithme | Complexité asymptotique |
|---|---|
| Multiplication classique | O(n2) |
| Karatsuba | O(n^1,585) |
| Toom-Cook | O(n^1,465) |
| Schönhage-Strassen | O(n log n log log n) |
| Fürer | proche de O(n log n) |
| Harvey-van der Hoeven | O(n log n) |
La complexité de Schönhage-Strassen constitue une amélioration spectaculaire par rapport aux méthodes précédentes. Pour des nombres contenant plusieurs centaines de milliers de chiffres, cette différence représente des millions, voire des milliards d'opérations économisées.
Avantages
La multiplication de Schönhage-Strassen présente de nombreux avantages :
- elle est extrêmement rapide pour les très grands entiers ;
- elle réduit fortement le nombre de multiplications nécessaires ;
- elle produit des résultats exacts grâce à l'utilisation de l'arithmétique modulaire ;
- elle a constitué pendant plusieurs décennies la méthode de référence pour la multiplication multiprécision ;
- elle a inspiré la majorité des algorithmes modernes de multiplication rapide.
Inconvénients
Cette méthode possède également plusieurs limites :
- son implémentation est particulièrement complexe ;
- elle nécessite des connaissances avancées en théorie des nombres et en analyse numérique ;
- elle consomme davantage de mémoire que Karatsuba ou Toom-Cook ;
- elle est plus lente que les méthodes plus simples lorsque les nombres sont relativement petits ;
- son intérêt apparaît uniquement lorsque les opérandes deviennent très grands.
Pour cette raison, les bibliothèques multiprécision utilisent généralement plusieurs algorithmes différents selon la taille des nombres.
Applications
La multiplication de Schönhage-Strassen est utilisée dans de nombreux domaines nécessitant des calculs sur des entiers gigantesques :
- bibliothèques de calcul multiprécision ;
- cryptographie (RSA, Diffie-Hellman, ECC) ;
- calcul scientifique ;
- logiciels de calcul symbolique ;
- théorie des nombres ;
- démonstrations mathématiques assistées par ordinateur ;
- recherche en informatique théorique ;
- logiciels de calcul haute précision.
Pendant de nombreuses années, elle a été intégrée dans plusieurs bibliothèques spécialisées, notamment GNU Multiple Precision (GMP), qui l'utilisait au-delà d'un certain seuil de taille avant l'apparition d'algorithmes plus récents.
Comparaison avec les autres méthodes
| Algorithme | Domaine d'utilisation |
|---|---|
| Multiplication naïve | Enseignement et petits calculs |
| Multiplication russe | Optimisation simple des additions |
| Karatsuba | Grands entiers |
| Toom-Cook | Très grands entiers |
| Schönhage-Strassen | Entiers gigantesques |
| Fürer | Recherche théorique |
| Harvey-van der Hoeven | État actuel de la recherche théorique |
Dans les bibliothèques modernes, le choix de l'algorithme est entièrement automatique. Les petits nombres utilisent la multiplication classique, les nombres intermédiaires utilisent Karatsuba ou Toom-Cook, tandis que les très grands entiers sont confiés à des méthodes fondées sur la FFT, parmi lesquelles Schönhage-Strassen a longtemps occupé une place centrale.
Remarque
Même si les travaux de Martin Fürer puis de David Harvey et Joris van der Hoeven ont permis d'améliorer la complexité théorique de la multiplication des très grands entiers, la méthode de Schönhage-Strassen demeure une étape fondamentale de l'histoire de l'informatique. Elle a démontré qu'il était possible d'exploiter les transformées rapides pour accélérer considérablement les opérations arithmétiques et a servi de fondement à une grande partie des recherches modernes sur la multiplication multiprécision. Aujourd'hui encore, ses principes influencent la conception de nombreuses bibliothèques de calcul scientifique et d'arithmétique avancée.