Pour l'utilisation de la transformée de Fourier rapide : multiplier des nombres décomposés en base quelconque, par exemple, ça revient à multiplier des polynômes, puis à effectuer les retenues.
Or, la convolution cyclique, dans l'espace de Fourier, c'est une multiplication terme à terme.
Bref, pour multiplier des grands nombres, on passe en Fourier, on multiplie terme à terme, on retourne dans l'espace normal, on effectue les retenues, et on ajoute ou retire un module pour corriger l'utilisation d'une convolution linéaire.
[^] # Re: N'est stupide que la stupidité :)
Posté par 🚲 Tanguy Ortolo (site web personnel) . En réponse à la dépêche Go-oo, une alternative à OpenOffice. Évalué à 5.
Or, la multiplication de polynômes, c'est une convolution linéaire. Et à en croire l'explication de l'algorithme de Schönhage-Strassen (http://en.wikipedia.org/wiki/Sch%C3%B6nhage-Strassen_algorit(...) on peut s'y ramener par une convolution cyclique normale.
Or, la convolution cyclique, dans l'espace de Fourier, c'est une multiplication terme à terme.
Bref, pour multiplier des grands nombres, on passe en Fourier, on multiplie terme à terme, on retourne dans l'espace normal, on effectue les retenues, et on ajoute ou retire un module pour corriger l'utilisation d'une convolution linéaire.