I'm trying to understand how to compute a fast Fourier transform over a finite field. This question arose in the analysis of some BCH codes.

Consider the finite field $F$ with $2^n$ elements. It is possible to define a (discrete) Fourier transform on vectors of length $2^n-1$ as follows. Choose a $2^n-1$ root of unity $\omega\in F$. Then given a vector $V=(V_0,...,V_{2^n-2})\in F^{2^n-1}$, we can define its Fourier transform $W=(W_0,...,W_{2^n-2}) \in F^{2^n-1}$ as: $$W_i=\sum_{j=0}^{2^n-2} \omega^{ij} V_j$$ To find such an $\omega$ we can use any primitive elements of $F$.

Suppose we are given $V$ and we would like to compute efficiently $W$. If we were operating over the complex numbers, we could choose any of a number of fast Fourier transform algorithms. The mixed radix Cooley-Tukey algorithm translates unchanged in this context, so if $2^n-1$ is the product of small factors (i.e. is smooth), then we are all set.

However, $2^n-1$ may be prime (after all, these numbers include the Mersenne primes) or contain large prime factors. The traditional Cooley-Tukey algorithm is no longer efficient. Over the complex numbers, this does not pose a problem-- there exist fast algorithms (like Bluestein's algorithm and Rader's algorithm) for handling that case. These algorithms typically involve rephrasing an $N$-point Fourier transform as a convolution, and evaluating the convolution by performing a $2^m$ point FFT, where $2^m\geq 2N-1$.

Unfortunately for us, there is no $2^m$ root of unity in any finite field of characteristic 2. Adjoining such a root to our field produces a much larger ring, and the added complexity of handling these elements appears to cancel the speed-up we would have gotten from the FFT. In (1), Pollard suggests using Bluestein's algorithm, but his argument doesn't seem to apply to fields of characteristic 2 (unless I'm misunderstanding him).

My question is: in the case described above, how do I compute an fast Fourier transform? For my original purpose, I was hoping to find a radix-two algorithm, but at this point I'd be interested in any fast algorithm.

(1) J. M. Pollard. "The Fast Fourier Transform in a Finite Field". Mathematics of Computation, Vol. 25, No. 114 (Apr., 1971), pp. 365-374.

2more comments