**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
**

(33) |

(34) |

(35) |

(36) |

(37) |

(38) |

- evaluate at the even powers for , and
- evaluate at the odd powers for .

(39) |

- additions in ,
- multiplications by powers of .

(40) |

leading to the result by plugging in the induction hypothesis.

*
*

2008-01-07