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.
Best Answer
There are a few different approaches to this:
1) As Peter Shor mentioned you can use a $3^n$ point transform with Bluestein's algorithm.
2) Even though there are no $2^n$ roots of unity there are substitutes for them (first implicitly discussed by Leonard Carlitz, and then explicitly by David Cantor). Look here for a good account of this http://www.math.clemson.edu/~sgao/papers/GM10.pdf
This algorithm is most likely the most efficient one in practice.
3) There's an observation of Shmuel Winograd who noticed that, using the relation between multiplicative and additive characters you can convert an FFT on $N$ points to the calculation of a cyclic convolution on $N-1$ points. And $N-1$ might factor nicely.