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 :

As discussed above, a mixed-radix Cooley Tukey FFT can be used to implement a length DFT using DFTs of length . However, for factors of that are mutually prime (such as and for ), a more efficient 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.5Since 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].

---

Previous: Fixed-Point FFTs and NFFTs
Next: Rader's FFT Algorithm for Prime Lengths

Order a Hardcopy of Mathematics of the DFT

---

About the Author: Julius Orion Smith III
Julius Smith's background is in electrical engineering (BS Rice 1975, PhD Stanford 1983). He is presently Professor of Music and Associate Professor (by courtesy) of Electrical Engineering at Stanford's Center for Computer Research in Music and Acoustics (CCRMA), teaching courses and pursuing research related to signal processing applied to music and audio systems. See http://ccrma.stanford.edu/~jos/ for details.