Schönhage–Strassen algorithm

The Schönhage–Strassen algorithm is an asymptotically fast multiplication algorithm for large integers. It was developed by Arnold Schönhage and Volker Strassen in 1971. The run-time bit complexity is, in Big O notation,${\displaystyle O{\Big (}n\cdot \log(n)\cdot \log {\big (}\log(n){\big )}{\Big )}}$ for two n-digit numbers. The algorithm uses recursive Fast Fourier transforms in rings with 2ⁿ+1 elements, a specific type of number theoretic transform.

The Schönhage–Strassen algorithm was the asymptotically fastest multiplication method known from 1971 until 2007, when a new method, Fürer's algorithm, was announced with lower asymptotic complexity; however, Fürer's algorithm currently only achieves an advantage for astronomically large values and is not used in practice.

...
Wikipedia