Fast computation of discrete Fourier transforms using polynomial transforms

Polynomial transforms, defined in rings of polynomials, have been introduced recently and have been shown to give efficient algorithms for the computation of two-dimensional convolutions. In this paper we present two methods for computing discrete Fourier transforms (DFT) by polynomial transforms. We show that these techniques are particularly well adapted to multidimensional DFT's as well as to some one-dimensional DFT's and yield algorithms that are, in many instances, more efficient than the fast Fourier transform (FFT) or the Winograd Fourier Transform (WFTA). We also describe new split nesting and split prime factor techniques for computing large DFT's from a small set of short DFT's with a minimum number of operations.