Integer multiplication in time O(n log n)

Joris van der Hoeven and I recently discovered an algorithm that computes the product of two $n$-bit integers in $O(n \log n)$ bit operations. This is asymptotically faster than all previous known algorithms, and matches the complexity bound conjectured by Schönhage and Strassen in 1971.

In this talk, I will discuss the history of integer multiplication, and give an overview of the new algorithm. No previous background on multiplication algorithms will be assumed.

About the speaker

Dr David Harvey is an Associate Professor and ARC Future Fellow at the School of Mathematics and StatisticsUniversity of New South Wales.