Prime Factor Algorithm (PFA)

By the prime factorization theorem, every integer $N$ can be uniquely factored into a product of $n_N$ prime numbers $p_i$ raised to an integer power $m_i\ge 1$,

$$N = \prod_{i=1}^{n_p} p_i^{m_i}$$

Then a more efficient prime factor algorithm (PFA) can be constructed from a collection of length $p_i$ DFTs. The results of the smaller transforms may be combined via the Chinese Remainder Theorem.

It is interesting to note that the PFA actually predates the Cooley-Tukey FFT paper of 1965 [13], with Good's 1958 work on the PFA being cited in that paper [26].