[ Homepage | Publications | Talks | TeXmacs |
Mathemagix ] |

Let be the finite field with elements and let be a primitive -th root of unity in an extension field of . Given a polynomial of degree less than , we will show that its discrete Fourier transform can be computed essentially times faster than the discrete Fourier transform of a polynomial of degree less than , in many cases. This result is achieved by exploiting the symmetries provided by the Frobenius automorphism of over .

**Authors:**

**Keywords: **FFT, finite field, complexity bound,
Frobenius automorphism