## Prime Factor Algorithm (PFA)

By the prime factorization theorem, every integer can be uniquely factored into a product of prime numbers raised to an integer power :

*prime factor algorithm*(PFA), also called the

*Good-Thomas FFT algorithm*, can be used [26,80,35,43,10,83].

^{A.4}The Chinese Remainder Theorem is used to

*re-index*either the input or output samples for the PFA.

^{A.5}Since the PFA is only applicable to mutually prime factors of , it is ideally combined with a mixed-radix Cooley-Tukey FFT, which works for any integer factors.

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

The PFA and *Winograd transform* [43] are
closely related, with the PFA being somewhat faster [9].

**Next Section:**

Rader's FFT Algorithm for Prime Lengths

**Previous Section:**

Mixed-Radix Cooley-Tukey FFT