Integer multiplication and the truncated product problem

Abstract:

It is now over a decade since the appearance of Fürer's breakthrough result on the asymptotic complexity of integer multiplication. Over the past few years, several authors, building on Fürer's ideas, have proposed improved and simplified algorithms for this problem. I will give an overview of the current status of research in this area. I will also discuss recent progress on the problem of computing a truncated integer product, i.e., computing only the top half (or bottom half) of the product of two integers.