互質因子算法 互質因子算法Primefactor FFT algorithm PFA又稱為GoodThomas算法 是一種快速傅立葉變換FFT把N  NN大小的離散傅立葉變換重新表示為N  N大小的二維離散傅立葉變換其中N與N需互質變成N和N大小的傅立葉變換後可以繼續遞迴使用PFA或用其他快速傅立葉變換算法來計算 較流行的CooleyTukey算法經由mixedradix一般化後也是把N  NN大小的離散傅立葉變換分割為N和N大小的轉換但和互質因子算法 PFA作法並不相同不應混淆CooleyTukey算法的N與N不需互質可以是任何整數然而有個缺點是比PFA多出一些乘法和單位根twiddle factors相乘相對的PFA的缺點則是N與N需互質 例如N 是次方就不適用而且要藉由中國剩餘定理來進行較複雜的reindexing互質因子算法 PFA可以和mixedradix CooleyTukey算法相結合前者將N 分解為互質的因數後者則用在重複質因數上 PFA也與nested Winograd FFT算法密切相關後者使用更為精巧的二維摺積技巧分解成N  N的轉換因而一些較古老的論文把Winograd算法稱為PFA FFT 儘管PFA和CooleyTukey算法並不相同但有趣的是Cooley和Tukey在他們年發表的有名的論文中沒有發覺到高斯和其他人更早的研究只引用Good在年發表的PFA作為前人的FFT結果剛開始的時候人們對這兩種作法是否不同有點困惑