Free Books
   Free Books    Mathematics of the DFT  

Rader's FFT Algorithm for Prime Lengths

Rader's FFT algorithm can be used to compute DFTs of length $ N$ in $ {\cal O}(N\lg N)$ operations when $ N$ is a prime number. For an introduction, see the Wikipedia page for Rader's FFT Algorithm:

http://en.wikipedia.org/wiki/Rader's_FFT_algorithm

Next Section:
Bluestein's FFT Algorithm
Previous Section:
Prime Factor Algorithm (PFA)