Yup. And you can then use the FFT to do super-fast multiplication. (I think you omitted something like "pointwise multiplication" after "equivalent of".) This i

Yup. And you can then use the FFT to do super-fast multiplication. (I think you omitted something like "pointwise multiplication" after "equivalent of".) This is called "Strassen multiplication"; you can actually do better by doing your Fourier transforms not with complex numbers but with a different algebraic structure; that's called Schönhage-Strassen multiplication. I've seen it claimed that Strassen is actually faster in practice than Schönhage-Strassen. Your numbers need to be pretty big before the benefits of this sort of algorithm outweigh the overheads, though. For instance, GMP uses naive multiplication up to about 600 bits, various Karatsuba/Toom-Cook schemes (divide-and-conquer) up to about 120,000 bits, and FFT after that.