Fürer's algorithm

The Schönhage–Strassen algorithm uses the fast Fourier transform (FFT) to compute integer products in time ${\displaystyle O(n\log n\cdot \log \log n)}$ and its authors, Arnold Schönhage and Volker Strassen, conjecture a lower bound of ${\displaystyle \Omega (n\log n)}$. Fürer's algorithm reduces the gap between these two bounds. It can be used to multiply integers of length ${\displaystyle n}$ in time ${\displaystyle O\left(n\log n\ \cdot 2^{O(\log ^{*}n)}\right)}$ where log*n is the iterated logarithm. The difference between the ${\displaystyle \log \log n}$ and ${\displaystyle 2^{\log ^{*}n}}$ terms, from a complexity point of view, is asymptotically in the advantage of Fürer's algorithm for integers greater than ${\displaystyle 2^{2^{64}}}$. However the difference between these terms for realistic values of ${\displaystyle n}$ is very small.[1]

In 2008 De et al gave a similar algorithm which relies on modular arithmetic instead of complex arithmetic to achieve in fact the same running time.[3] It has been estimated that it becomes faster than Schönhage-Strassen for inputs exceeding a length of ${\displaystyle 10^{10^{4796}}}$.[4]

In 2015 Harvey, Joris van der Hoeven and Lecerf[5] gave a new algorithm that achieves a running time of ${\displaystyle O(n\log n\cdot 2^{3\log ^{*}n})}$ making explicit the implied constant in the ${\displaystyle O(\log ^{*}n)}$ exponent. They also proposed a variant of their algorithm which achieves ${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$ but whose validity relies on standard conjectures about the distribution of Mersenne primes.

In 2015 Covanov and Thomé provided another modification of Fürer's algorithm which achieves the same running time.[6] Nevertheless, it remains just as impractical as all the other implementations of this algorithm.[7][8]

In 2016 Covanov and Thomé proposed an integer multiplication algorithm based on a generalization of Fermat primes that conjecturally achieves a complexity bound of ${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$. This matches the 2015 conditional result of Harvey, van der Hoeven, and Lecerf but uses a different algorithm and relies on a different conjecture.[9]

In 2018 Harvey and van der Hoeven used an approach based on the existence of short lattice vectors guaranteed by Minkowski's theorem to prove an unconditional complexity bound of ${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$.[10]

In March 2019, Harvey and van der Hoeven published a long-sought after ${\displaystyle O(n\log n)}$ integer multiplication algorithm, which is conjectured to be asymptotically optimal.[11][12] Because Schönhage and Strassen predicted that n log(n) is the ‘best possible’ result Harvey said: “...our work is expected to be the end of the road for this problem, although we don't know yet how to prove this rigorously.”[13]

• Number-theoretic transform