Schonhage-Strassen Algorithm

The Schonhage-Strassen algorithm is an asymptotically fast multiplication algorithm for large integers, published by Arnold Schonhage and Volker Strassen in 1971, which works by recursively applying the fast Fourier transform over the integers modulo two to the power n plus one. It was the asymptotically fastest known multiplication method from 1971 until 2007 and remains asymptotically faster than older methods such as the Karatsuba algorithm and Toom-Cook multiplication, outperforming them in practice for numbers beyond roughly ten thousand to one hundred thousand decimal digits.