HomepagePublicationsTalksTeXmacsMathemagix |

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 .

**Occasion:** ISSAC 2017, Kaiserslautern, Germany, July 27,
2017

**Documents:** slideshow, TeXmacs
source