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: Joris van der Hoeven, Robin Larrieu

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

View: Html, TeXmacs, Pdf, BibTeX