Chapter 1 [1] of Chee Yap's "Fundamental Problems of Algorithmic Algebra" [2] gives integer multiplication at O(n lg(n) lg(lg(n))). To prove that bound a "disc

Chapter 1 [1] of Chee Yap's "Fundamental Problems of Algorithmic Algebra" [2] gives integer multiplication at O(n lg(n) lg(lg(n))). To prove that bound a "discrete Fourier transform" is used using modular arithmetic over 2^L + 1 (for suitable L). As you say, you can always convert to an integer multiplication problem so it stands at O(n lg(n) lg(lg(n))) (not O(n lg^2(n))). [1] http://cs.nyu.edu/~yap/book/alge/ftpSite/l1.ps.gz http://cs.nyu.edu/~yap/book/alge/ftpSite/l1.ps.gz [2] https://www.cs.nyu.edu/yap/book/berlin/ https://www.cs.nyu.edu/yap/book/berlin/