Schönhage–Strassen algorithm

Common card · No. 270864

The Schönhage–Strassen algorithm is an asymptotically fast multiplication algorithm for large integers, published by Arnold Schönhage and Volker Strassen in 1971. It works by recursively applying fast Fourier transform (FFT) over the integers modulo 2 n + 1 {\displaystyle 2^{n}+1} . The run-time bit complexity to multiply two n-digit numbers using the algorithm is O ( n ⋅ log ⁡ n ⋅ log ⁡ log ⁡ n ) {\displaystyle O(n\cdot \log n\cdot \log \log n)} in big O notation. The Schönhage–Strassen algorithm was the asymptotically fastest multiplication method known from 1971 until 2007. It is asymptotically faster than older methods such as Karatsuba and Toom–Cook multiplication, and starts to outperform them in practice for numbers beyond...

Read on Wikipedia · Image Dcoetzee, CC0