Fast Multiplication of Large Integers: An English translation of “Schnelle Multiplikation großer Zahlen”

This is an English translation of Schönhage and Strassen’s classic 1971 paper “Schnelle Multiplikation großer Zahlen” in which they described what is now known as the Schönhage–Strassen algorithm, which is currently (as of May 22, 2023) the fastest known algorithm in practice for multiplying large integers (according to Wikipedia, for integers larger than 10,000–100,000 decimal digits). It has time complexity $O(n \log n \log \log n)$. The algorithm with the best known computational complexity is the Harvey–Hoeven algorithm published in 2019, which has complexity $O(n \log n)$, but is not used in practice due to its large constant factors.

I was unable to find an English translation of this classic paper, so I made one myself by typing up the original equations in LaTeX and using ChatGPT to translate the text. Efficient multiplication algorithms (particularly for matrices, used extensively in AI technology) are currently of great importance to society. I am uploading this translation in the hopes that it allows others to enjoy and maybe even improve upon this classic paper.

This translation is licensed under the CC BY license; however, the original paper may still be under copyright in your jurisdiction.

Shield:

This work is licensed under a Creative Commons Attribution 4.0 International License.