^{ log*(n)}) time.

In 1971, Schonhage and Strassen developed an algorithm to multiply two n-bit integers in O(n log(n) log(log(n))) time. In the same paper, they conjectured that the actual bound was Theta(n log(n)). In 2007, this result was sharpened to O(n log(n) * K

^{log*(n)}) for some unspecified K > 1. Very recently, in 2018-2019, this bound was improved to O(n log(n) * 4

^{ log*(n)}).

The only lower bounds are linear. The trivial lower bound follows from the fact that we have to examine each bit, and there are 2n bits (given two n-bit integers).

Here is a link to the paper, in case anyone is interested. It is 43 pages and uses a lot of heavy-handed techniques, including algebra, Fourier analysis, and numerical approximations over the complex numbers.

https://hal.archives...070778/document

This post has been edited by **macosxnerd101**: 07 April 2019 - 03:54 PM