Very fast discrete Fourier transform using number theoretic transform
Wan-Chi Siu, Anthony George Constantinides · IEE Proceedings G (Electronic Circuits and Systems) · 1983
It is shown that number theoretic transforms (NTT) can be used to compute discrete Fourier transform (DFT) very efficiently. By noting some simple properties of number theory and the DFT, the total number of real multiplications for a length-P DFT is reduced to (P − 1). This requires less than one real multiplications per point. For a proper choice of transform length and NTT, the number of shift adds per point is approximately the same as the number of additions required for FFT algorithms.