The best known algorithm for it requires a twiddle factor to separate a sum over a certain complex exponential, that algorithm is named for Cooley and Tukey.
A similar operation named for Hartley was proven not to be faster than this operation in 1987 by Duhamel and Vetterli. A Cunningham sequence of Sophie Germain primes leads to poor performance of this by Rader's algorithm, which works by changing prime lengths into convolutions. The Winograd method allows decimation by several different factors, and is an extension of the Danielson-Lanczos Lemma which allows a problem of length to be replaced by two problems of length N over two. The best known algorithm for it requires a twiddle factor to separate a sum over a certain complex exponential, that algorithm is named for Cooley and Tukey. FTP, name this efficient method to computer a certain discrete transform between time and frequency domain.
A similar operation named for Hartley was proven not to be faster than this operation in 1987 by Duhamel and Vetterli.
{Fast Fourier} Transform [accept {FFT}, prompt on {Discrete} "{Fourier}" {Transform}]