n-digit integers can be multiplied in n log n 2^O(log*n) operations

You need to know: Integer multiplication, algorithm, running time of an algorithm, logarithm, big O notation.

Background: The iterated logarithm $\log^*$ is the unique function which has properties (i) $\log^*n =0$ if $n\leq 1$ and (ii) $\log^*n = 1+\log^*(\log n)$ if $n>1$ .

The Theorem: On 27th December 2007, Martin Fürer submitted to SIAM Journal on Computing a paper in which he presented a new algorithm for multiplying integers and proved that its running time is $n\log n 2^{O(\log^*(n))}$ for n-digit integers.

Short context: Integer multiplication is one of the basic operations in mathematics. Usual school method requires $O(n^2)$ operations for n-digit integers. In 1971, Schönhage and Strassen presented a much faster $O(n \log n \log\log n)$ algorithm, and conjectured that $O(n \log n)$ algorithm should exist. This algorithm remained the fastest one for 36 years. The Theorem presents a faster method whose running time is very close to $O(n \log n)$ . In a later work, David Harvey and Joris van der Hoeven removed the $2^{O(\log^*(n))}$ factor and presented the $O(n \log n)$ algorithm.