The predecessor to the Fürer algorithm, the Schönhage-Strassen algorithm, used fast Fourier transforms to compute integer products in time (in big O notation) and its authors, Arnold Schönhage and Volker Strassen, also conjectured a lower bound for the problem of . Here, denotes the total number of bits in the two input numbers. Fürer's algorithm reduces the gap between these two bounds: it can be used to multiply binary integers of length in time (or by a circuit with that many logic gates), where log*n represents the iterated logarithm operation. However, the difference between the and factors in the time bounds of the Schönhage-Strassen algorithm and the Fürer algorithm for realistic values of is very small.
In 2008, Anindya De, Chandan Saha, Piyush Kurur and Ramprasad Saptharishi gave a similar algorithm that relies on modular arithmetic instead of complex arithmetic to achieve the same running time.