Two-dimensional discrete Fourier transform with small multiplicative complexity using number theoretic transforms

The conventional approach to computing the 2-D discrete Fourier transform (DFT) by row column or nesting algorithms is still computationally demanding because of the excessive number of multiplications required. It is shown that the number theoretic transform (NTT) can be used to compute the 2-D DFT very efficiently, with less than one multiplication per point. The technique makes use of index mapping for efficient calculation of convolution as a subset of transform computations.