互質因子算法

互质因子算法（Prime-factor FFT algorithm, PFA），又称为Good-Thomas算法，是一种快速傅立叶变换（FFT），把N = N₁N₂大小的离散傅立叶变换重新表示为N₁ * N₂大小的二维离散傅立叶变换，其中N₁与N₂需互质。变成N₁和N₂大小的傅立叶变换后，可以继续递回使用PFA，或用其他快速傅立叶变换算法来计算。
较流行的Cooley-Tukey算法经由mixed-radix一般化后，也是把N = N₁N₂大小的离散傅立叶变换分割为N₁和N₂大小的转换，但和互质因子算法(PFA)作法并不相同，不应混淆。Cooley-Tukey算法的N₁与N₂不需互质，可以是任何整数。然而有个缺点是比PFA多出一些乘法，和单位根twiddle factors相乘。相对的，PFA的缺点则是N₁与N₂需互质 (例如N 是2次方就不适用)，而且要借由中国剩余定理来进行较复杂的re-indexing。互质因子算法(PFA)可以和mixed-radix Cooley-Tukey算法相结合，前者将N 分解为互质的因数，后者则用在重复质因数上。
PFA也与nested Winograd FFT算法密切相关，后者使用更为精巧的二维折积技巧分解成N₁ * N₂的转换。因而一些较古老的论文把Winograd算法称为PFA FFT。
尽管PFA和Cooley-Tukey算法并不相同，但有趣的是Cooley和Tukey在他们1965年发表的有名的论文中，没有发觉到高斯和其他人更早的研究，只引用Good在1958年发表的PFA作为前人的FFT结果。刚开始的时候人们对这两种作法是否不同有点困惑。

范例

以N = 6为例，有两种可能，N₁ = 2, N₂ = 3或N₁ = 3, N₂ = 2。
第一种情形所产生的流程图如左图所示。先做2次3点DFT后再做3次2点DFT。
第二种情形所产生的流程图如右图所示。先做3次2点DFT后再做2次3点DFT。
其中2点DFT的部分因构造单纯，皆以交错的蝴蝶图来显示。
可以看出即使在这个简单的例子中，输入和输出的index也都经过有点复杂的重新排列。