The Frobenius FFT
Joris van der Hoeven, Robin Larrieu · 2017
Let Fq be the finite field with q elements and let ω be a primitive n-th root of unity in an extension field Fqd of Fq. Given a polynomial P ∈ Fq [x] of degree less than n, we will show that its discrete Fourier transform (P (ω0), ..., P (ωn - 1)) ∈ Fqdn can be computed essentially d times faster than the discrete Fourier transform of a polynomial Q ∈ Fqd [x] of degree less than n, in many cases. This result is achieved by exploiting the symmetries provided by the Frobenius automorphism of Fqd over Fq.