A Method for Fast Computation of the Fourier Transform over a Finite Field (2003)

by Peter Trifonov. S. V. Fedorenko.

Problems of Information Transmission

We consider the problem of fast computation of the Fourier transform over a finite field by decomposing an arbitrary polynomial into a sum of linearized polynomials. Examples of algorithms for the Fourier transform with complexity less than that of the best known analogs are given. Presently, a number of fast Fourier transform (FFT) algorithms over the real or complex field is known, but translation of these algorithms to finite fields is not always possible. Furthermore, an FFT algorithm specially constructed for a particular finite field may be better than an algorithm translated from another field [1]. [via]

http://dcn.infos.ru/~petert/papers/fftEng.pdf...