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