## The Fast Fourier Transform

The Fast Fourier Transform computes the DFT quickly. This important algorithm for computer science (not only computer algebra, but also digital signal processing for instance) was (re)-discovered in 1965 by Cooley and Tukey.

Let be a positive even integer, be a primitive -th root of unity and . In order to evaluate at , we follow a divide-and-conquer strategy; more precisely, we consider the divisions with remainder of by and . So let be polynomials such that

 (31)

and

 (32)

The relations and hold because the polynomial has degree less than . Observe that the computation of and can be done very easily. Indeed, let be such that

 (33)

We have

 (34)

Hence we obtain

 (35)

Let be an integer such that . By using Relation (31) with we obtain

 (36)

since . Then, by using Relation (32) with we obtain

 (37)

since . Indeed, this last equation follows from

 (38)

and the fact that is not zero nor a zero divisor. Therefore we have proved the following

Proposition 4   Evaluating (with degree less than ) at is equivalent to
• evaluate at the even powers for , and
• evaluate at the odd powers for .

Since it is easy to show that is a primitive -th root of unity we can hope for a recursive algorithm. This algorithm would be easier if both and would be evaluated at the same points. So we define

 (39)

Now we obtain the following algorithm.

Algorithm 1

Theorem 1   Let be a power of and be a primitive -th root of unity. Then Algorithm 1 computes using
• additions in ,
• multiplications by powers of .
leading in total to ring operations.

Proof. By induction on . Let and be the number of additions and multiplications in that the algorithms requires for an input of size . If the algorithm returns whose costs is null thus we have and which satisfies the formula since . Assume . Just by looking at the algorithm we that

 (40)

leading to the result by plugging in the induction hypothesis.

Marc Moreno Maza
2008-01-07