I was under the impression that because the grade school technique we learn is really just convolution over the digits, the fastest algorithms achieve o(n logn) via fourier transforms. Is that not the case?
I just looked up the answer to my original question - the Fourier trick is notionally only O(N logN), but because the FFT takes you from integers to floating points, as N gets larger you need to encode more and more bits to achieve enough precision to yield absolute errors <1 after doing both Fourier transforms. The need to encode those extra bits tacks on another logN, taking you to O(N log^2 N).