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 Swiss

Switzerland

Switzerland name of one of the Swiss cantons. ; ; ; or ), in its full name the Swiss Confederation , is a federal republic consisting of 26 cantons, with Bern as the seat of the federal authorities. The country is situated in Western Europe,Or Central Europe depending on the definition....

 mathematician Martin Fürer of Pennsylvania State University

Pennsylvania State University

The Pennsylvania State University, commonly referred to as Penn State or PSU, is a public research university with campuses and facilities throughout the state of Pennsylvania, United States. Founded in 1855, the university has a threefold mission of teaching, research, and public service...

 as an asymptotically faster (when analysed on a multitape Turing machine) 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 transform

Fast Fourier transform

A fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. "The FFT has been called the most important numerical algorithm of our lifetime ." There are many distinct FFT algorithms involving a wide range of mathematics, from simple...

s to compute integer products in time in big O notation

Big O notation

In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...

 and its authors, Arnold Schönhage

Arnold Schönhage

Arnold Schönhage is a mathematician and computer scientist and Professor Emeritus at Rheinische Friedrich-Wilhelms-Universität, Bonn. He was also professor in Tübingen and Konstanz...

 and Volker Strassen

Volker Strassen

Volker Strassen is a German mathematician, a professor emeritus in the department of mathematics and statistics at the University of Konstanz.-Biography:Strassen was born on April 29, 1936, in Düsseldorf-Gerresheim....

, 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 $n\; \backslash log\; n\backslash ,2^\{O(\backslash log^*\; n)\}$ (or by a circuit

Boolean circuit

A Boolean circuit is a mathematical model of computation used in studying computational complexity theory. Boolean circuits are the main object of study in circuit complexity and are a special kind of circuits; a formal language can be decided by a family of Boolean circuits, one circuit for each...

 with that many logic gates), where represents the iterated logarithm

Iterated logarithm

In computer science, the iterated logarithm of n, written  n , is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1...

 operation. However, the difference between the and $2^\{\backslash log^*\; n\}$ 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

Modular arithmetic

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....

instead of complex arithmetic to achieve the same running time.