20
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ Can you use a 3$^m$ (or other smooth number) point FFT for evaluating the convolution in Bluestein's algorithm or Rader's algorithm $\endgroup$
    – Peter Shor
    Commented Sep 29, 2010 at 18:50
  • $\begingroup$ If we could efficiently construct some smooth root of unity of size $\geq 2N-1$, then we could use Bluestein's algorithm. If we extend our field $F$ to a larger field, we might luck out and find such a root, but I don't know how to guarantee the existence of a sufficiently large but smooth root of unity. (The field extension can't be too large, either, or our computation will slow down on that front.) But perhaps we could extend to a ring instead of a field? $\endgroup$
    – Bill Bradley
    Commented Sep 30, 2010 at 11:19
  • 1
    $\begingroup$ So this brings us to a question of estimating the probability you get a smooth root of unity in not-too-large extensions of a finite field. My intuition is that, even if they're not guaranteed by number theory guaranteed to exist, they will with very high probability exist. (And finding them should be easy, because testing for smooth factors of a number is efficient). Are there any number theorists reading this? If not, you could formulate a new question which specifically addresses the number theory aspects, and ask it on MO. $\endgroup$
    – Peter Shor
    Commented Sep 30, 2010 at 13:17
  • 1
    $\begingroup$ Let me take that back. I really don't know the answer to this question; I just realized my intuition was quite possibly wrong. $\endgroup$
    – Peter Shor
    Commented Sep 30, 2010 at 18:12
  • $\begingroup$ Thanks-- I added "number-theory" as a category with the hope of getting some more help. I posted a related question on MO (with this application in mind): mathoverflow.net/questions/38586/smoothness-in-mersenne-numbers $\endgroup$
    – Bill Bradley
    Commented Oct 1, 2010 at 11:20

4 Answers 4

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Victor, do you know of any tables of indefinite ternary quadratic forms? There are tables of positive forms up to reasonable discriminant bounds on Sloane's website, so I will check that with the word indefinite and see what happens. Will $$ $$ $$ $$ $\endgroup$
    – Will Jagy
    Commented Oct 1, 2010 at 20:49
  • $\begingroup$ Thanks, Victor! The paper you referenced by Gao and Mateer is great. One interesting point in their paper bears on the the issue of using a $3^n$th root of unity. Gao and Mateer claim that "When $n$ is a power of 3, $F_2^k$ must have a value for $k$ as big as $2n=3$ to contain an $n$th root of unity, so the field size has to be exponential in $n$". $\endgroup$
    – Bill Bradley
    Commented Oct 4, 2010 at 18:59
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Multiplying two n bit numbers is at least O(n lg n lg lg n) once n leaves the size of your machine word. In fact, the fastest digit multiplying algorithm ends up being a FFT for extremely large n. For smaller n, Karatsuba is a touch under O(n^1.6). $\endgroup$
    – Yakk
    Commented Aug 25, 2014 at 11:29
1
$\begingroup$

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).

Improve this answer
$\endgroup$
0
$\begingroup$

You may use Gao-Mateer Additive algos. It almost like radix-2 but uses some x^2-x series instead roots of unity.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .