Speaking of incredibly cool algorithms based on Fourier transforms, the Schoenage-Strassen algorithm for multiplying integers is also amazing:
http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen...
At least to me, it seems hard to imagine that multiplying two N-bit integers could be done with less than O(N^2) operations. Schoenage-Strassen lets you do it using O(N log N log log N) operations!