FFTs over finite fields? 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.
 A: For finite fields of characteristic 2, the classic result is as far as I know 
@article{Schonhage:1976,
 author = {A. Sch\"{o}nhage},
 title = {Schnelle Multiplikation von Polynomen \"{u}ber K\"{o}rpern der Charakteristik 2},
 journal = {Acta Inform.},
 volume = {7},
  year = {1976},
 pages = {395--398},
 }
(in German)
Here an extra log log factor appears in the complexity compared with the classically quoted O(n log n) complexity over complex numbers.  The most general result (although about multiplication) appears to be
@article{123568,
 author = {Cantor, David G. and Kaltofen, Erich},
 title = {On fast multiplication of polynomials over arbitrary algebras},
 journal = {Acta Inf.},
 volume = {28},
 number = {7},
 year = {1991},
 issn = {0001-5903},
 pages = {693--701},
 doi = {http://dx.doi.org/10.1007/BF01178683},
 publisher = {Springer-Verlag New York, Inc.},
 address = {Secaucus, NJ, USA},
 }
with the same O(n log n log log n) complexity for a remarkably wide class of algebras.
Crandall and Pomerance's book Prime Numbers: A Computational Perspective  is also very helpful on this topic.
However, it is worth considering the complexities in more detail for a moment and what one's assumptions are about the computational model. All the complexities classically quoted refer to the Turing machine model. However, standard multiplication of two n bit numbers, for example, is in fact an O(n) time operation in the now popular unit cost RAM model by using simple bit packing.  If one is worrying about log factors, then this sort of issue becomes relevant for the FFT too.     
A: 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.
A: if you use a Galois field GF(p^2), where p is a Mersenne prime, this field it will contain the desired convenient roots of unity (since p^2-1 has a large power of 2, i.e. 2*(p+1),  as a factor).
A: You may use Gao-Mateer Additive algos. It almost like radix-2 but uses some x^2-x series instead roots of unity.
