Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Fast Polynomial Algorithms over all Finite Fields

Eli Ben-Sasson, Dan Carmon, Swastik Kopparty +1

For smooth finite fields $F_q$ (i.e., when $q-1$ factors into small primes) the Fast Fourier Transform (FFT) leads to the fastest known algebraic algorithms for many basic polynomi…