Apparently this FFT was first discovered by Gauss (1805). http://www.cis.rit.edu/class/simg716/Gauss_History_FFT.pdf http://www.cis.rit.edu/class/simg716/Gauss_

Apparently this FFT was first discovered by Gauss (1805). http://www.cis.rit.edu/class/simg716/Gauss_History_FFT.pdf http://www.cis.rit.edu/class/simg716/Gauss_History_FFT.pdf As a follow-up, let me recommend Püschel & Moura (2006) “Algebraic Signal Processing Theory”, https://arxiv.org/pdf/cs/0612077.pdf https://arxiv.org/pdf/cs/0612077.pdf and Püschel’s other papers about similar topics. Or in a different direction, DJB (2008), “Fast multiplication and its applications”, http://cr.yp.to/lineartime/multapps-20080515.pdf http://cr.yp.to/lineartime/multapps-20080515.pdf