http://www.cis.rit.edu/class/simg716/Gauss_History_FFT.pdf
As a Gauss fanboy let me just say wow. Especially note that from 1828 to 1965 there a various versions of the FFT presented for special cases but Gauss had the complete version in 1805.