Chapter 1 [1] of Chee Yap&#x27;s &quot;Fundamental Problems of Algorithmic Algebra&quot; [2] gives integer multiplication at O(n lg(n) lg(lg(n))).  To prove that bound a &quot;discrete Fourier transform&quot; is used using modular arithmetic over 2^L + 1 (for suitable L).<p>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))).<p>[1] <a href="http:&#x2F;&#x2F;cs.nyu.edu&#x2F;~yap&#x2F;book&#x2F;alge&#x2F;ftpSite&#x2F;l1.ps.gz" rel="nofollow">http:&#x2F;&#x2F;cs.nyu.edu&#x2F;~yap&#x2F;book&#x2F;alge&#x2F;ftpSite&#x2F;l1.ps.gz</a><p>[2] <a href="https:&#x2F;&#x2F;www.cs.nyu.edu&#x2F;yap&#x2F;book&#x2F;berlin&#x2F;" rel="nofollow">https:&#x2F;&#x2F;www.cs.nyu.edu&#x2F;yap&#x2F;book&#x2F;berlin&#x2F;</a>