La complexité de la multiplication

Multiplier deux nombres de n chiffres coûte naturellement n² opérations. Pour les très grands nombres, ce coût devient prohibitif : un milliard de chiffres demanderait 32 ans avec la méthode scolaire. Depuis 1971, l'algorithme de Schönhage-Strassen améliore cela (complexité en n log n log(log n)), mais la conjecture affirmait qu'on pourrait atteindre n log n.

Joris van der Hoeven et David Harvey ont relevé ce défi en généralisant la transformée de Fourier rapide (FFT) à plusieurs variables. Au lieu de traiter un nombre comme un polynôme à une variable, ils l'ont considéré comme un polynôme multidimensionnel, exploitant mieux les propriétés de la FFT et atteignant enfin la complexité n log n conjecturée.

Cependant, passer de la théorie à l'implémentation pratique pose des défis. L'algorithme privilégie les additions sur les multiplications, ce qui était avantageux il y a vingt ans quand les multiplications coûtaient beaucoup plus cher. Aujourd'hui, les processeurs modernes accélèrent la multiplication, réduisant l'intérêt pratique de cet algorithme.