Fast Fourier transform via automorphism groups of rational function fields

Songsong Li, Chaoping Xing

The Fast Fourier Transform (FFT) over a finite field ${\mathbb{F}}_q$ computes evaluations of a given polynomial of degree less than $n$ at a specifically chosen set of $n$ distinct…