fast fourier transforms over poor fields
We present a new algebraic algorithm for computing the discrete Fourier transform over arbitrary fields. It computes DFTs of infinitely many orders n in O ( n log n ) algebraic operations, while the complexity of a straightforward application of the known FFT algorithms can be ?( n 1.5 ) for such n . Our algorithm is a novel combination of the classical FFT algorithms, and is never slower than any of the latter. As an application we come up with an efficient way of computing DFTs of high orders in finite field extensions which can further boost polynomial multiplication algorithms. We relate the complexities of the DFTs of such orders with the complexity of polynomial multiplication.
fast fourier transforms finite fields complexity of polynomial multiplication algebraic complexity