ABSTRACT
The prime factor algorithms (PFAs) are specialized mixed-radix algorithms which are based on factoring the transform length into pairwise prime factors. This chapter considers some practical issues related to the performance of the prime factor algorithms, including the efficient implementation of the multi-factor PFA and the computation of short discrete Fourier transforms (DFTs) or short rotated DFTs in the PFA. When the three or more factors are pairwise prime, a multi-factor prime factor FFT can be implemented as a sequence of two-factor PFAs as noted by C. S. Burrus and P. W. Eschenbacher and C. Temperton. As to the theory behind the PFA, the chapter introduces a few relevant concepts from elementary number theory concerning the properties of integers. It aims to prove the Chinese Remainder Theorem (CRT), because CRT and CRT-related index maps are responsible for the number-theoretic splitting of the DFT matrix, which gives rise to the PFA.
