Fürer's algorithm

Fürer's algorithm is an integer multiplication algorithm for extremely large integers with very low asymptotic complexity. It was published in 2007 by the Swiss mathematician Martin Fürer of Pennsylvania State University as an asymptotically faster algorithm when analysed on a multitape Turing machine than its predecessor, the Schönhage–Strassen algorithm.

Background

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

Improved algorithms

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. It has been estimated that it becomes faster than Schönhage-Strassen for inputs exceeding a length of $10^{10^{4796}}$.

In 2015 Harvey, Joris van der Hoeven and Lecerf gave a new algorithm that achieves a running time of $O(n\log n\cdot 2^{3\log ^{*}n})$ making explicit the implied constant in the $O(\log ^{*}n)$ exponent. They also proposed a variant of their algorithm which achieves $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. Nevertheless, it remains just as impractical as all the other implementations of this algorithm.

In 2016 Covanov and Thomé proposed an integer multiplication algorithm based on a generalization of Fermat primes that conjecturally achieves a complexity bound of $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.

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 $O(n\log n\cdot 2^{2\log ^{*}n})$.

In March 2019, Harvey and van der Hoeven published a long-sought after $O(n\log n)$ integer multiplication algorithm, which is conjectured to be asymptotically optimal. 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.”

See also

• Number-theoretic transform