On the computation of discrete fourier transform using fermat number transform

In the paper the results of a study using Fermat number transforms (FNTs) to compute discrete Fourier transforms (DFTs) are presented. Eight basic FNT modules are suggested and used as the basic sequence lengths to compute long DFTs. The number of multiplications per point is for most cases not more than one, whereas the number of shift-adds is approximately equal to the number of additions in the Winograd-Fourier-transform algorithm and the polynomial transform. Thus the present technique is very effective in computing discrete Fourier transforms.