Definitions

Fürer's algorithm

Fürer's algorithm is an integer multiplication algorithm for very large numbers possessing a very low asymptotic complexity. It was created in 2007 by Martin Fürer of Pennsylvania State University as an asymptotically less-complex algorithm than its predecessor, the Schönhage-Strassen algorithm published in 1971.

The predecessor to the Fürer algorithm, the Schönhage-Strassen algorithm used fast Fourier transforms to compute integer products in time $O\left(n log n loglog n\right)$, and its authors, Arnold Schönhage and Volker Strassen, also conjectured a lower bound for the problem to be solved by an unknown algorithm as $O\left(n log n\right)$. Fürer's algorithm reduces the gap between these two bounds: it can be used to multiply binary integers of length n in time $n log n 2^\left\{O\left(log^* n\right)\right\}$ (or by a Boolean circuit with that many logic gates), where $log^* n$ represents the iterated logarithm operation. The difference between the $loglog n$ and $2^\left\{log^* n\right\}$ factors in the time bounds of the Schönhage-Strassen algorithm and the Fürer algorithm are so small that Fürer's algorithm would only speed up multiplication operations on "astronomically large numbers".