Fast fourier transforms over poor fields
Alexey Pospelov · 2011
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 Ω(n1.5) for such n. Our algorithm is a novel combination of the classical FFT algorithms, and is never slower than any of the latter.