Over finite fields $F_q$ containing a root of unity of smooth order $n$ (smoothness means $n$ is the product of small primes), the Fast Fourier Transform (FFT) leads to the fastest known algebraic algorithms for many basic polynomial operations, such as multiplication, division, interpolation and multi-point evaluation. These operations can be computed by constant fan-in arithmetic circuits over $F_q$ of quasi-linear size; specifically, $O(n \log n)$ for multiplication and division, and $O(n \log^2 n)$ for interpolation and evaluation.

However, the same operations over fields with no smooth order root of unity suffer from an asymptotic slowdown, typically due to the need to introduce “synthetic” roots of unity to enable the FFT. The classical algorithm of Schönhage and Strassen incurred a multiplicative slowdown factor of $\log \log n$ on top of the smooth case. Recent remarkable results of Harvey, van der Hoeven and Lecerf dramatically reduced this multiplicative overhead to $\exp(\log^* (n))$.

We introduce a new approach to fast algorithms for polynomial operations over all large finite fields. The key idea is to replace the group of roots of unity with a set of points $L \subset F_q$ suitably related to a well-chosen elliptic curve group over $F_q$ (the set L itself is not a group). The key advantage of this approach is that elliptic curve groups can be of any size in the Hasse–Weil interval $[q + 1 \pm 2\sqrt{q}]$ and thus can have subgroups of large, smooth order, which an FFT-like divide and conquer algorithm can exploit. Compare this with multiplicative subgroups over $F_q$ whose order must divide $q-1$. By analogy, our method extends the standard, multiplicative FFT in a similar way to how Lenstra’s elliptic curve method extended Pollard’s $p-1$ algorithm for factoring integers.

For polynomials represented by their evaluation over subsets of $L$, we show that multiplication, division, degree-computation, interpolation, evaluation and Reed–Solomon encoding (also known as low-degree extension) with fixed evaluation points can all be computed with arithmetic circuits of size similar to what is achievable with the classical FFTs when the field size $q$ is special. For several problems, this yields the asymptotically smallest known arithmetic circuits even in the standard monomial representation of polynomials.

The efficiency of the classical FFT follows from using the 2-to-1 squaring map to reduce the evaluation set of roots of unity of order $2^k$ to similar groups of size $2^{k?i}$, $i > 0$. Our algorithms operate similarly, using isogenies of elliptic curves with kernel size 2 as 2-to-1 maps to reduce $L$ of size $2^k$ to sets of size $2^{k?i}$ that are, like $L$, suitably related to elliptic curves, albeit different ones.

Added a discussion of the relation of our work to previous work by Chudnovsky & Chudnovsky (1989), see Section 1.3 and Appendix A.

Over finite fields $F_q$ containing a root of unity of smooth order $n$ (smoothness means $n$ is the product of small primes), the Fast Fourier Transform (FFT) leads to the fastest known algebraic algorithms for many basic polynomial operations, such as multiplication, division, interpolation and multi-point evaluation. These operations can be computed by constant fan-in arithmetic circuits over $F_q$ of quasi-linear size; specifically, $O(n \log n)$ for multiplication and division, and $O(n \log^2 n)$ for interpolation and evaluation.

However, the same operations over fields with no smooth order root of unity suffer from an asymptotic slowdown, typically due to the need to introduce “synthetic” roots of unity to enable the FFT. The classical algorithm of Schönhage and Strassen incurred a multiplicative slowdown factor of $\log \log n$ on top of the smooth case. Recent remarkable results of Harvey, van der Hoeven and Lecerf dramatically reduced this multiplicative overhead to $\exp(\log^* (n))$.

We introduce a new approach to fast algorithms for polynomial operations over all large finite fields. The key idea is to replace the group of roots of unity with a set of points $L \subset F_q$ suitably related to a well-chosen elliptic curve group over $F_q$ (the set L itself is not a group). The key advantage of this approach is that elliptic curve groups can be of any size in the Hasse–Weil interval $[q + 1 \pm 2\sqrt{q}]$ and thus can have subgroups of large, smooth order, which an FFT-like divide and conquer algorithm can exploit. Compare this with multiplicative subgroups over $F_q$ whose order must divide $q-1$. By analogy, our method extends the standard, multiplicative FFT in a similar way to how Lenstra’s elliptic curve method extended Pollard’s $p-1$ algorithm for factoring integers.

For polynomials represented by their evaluation over subsets of $L$, we show that multiplication, division, degree-computation, interpolation, evaluation and Reed–Solomon encoding (also known as low-degree extension) with fixed evaluation points can all be computed with arithmetic circuits of size similar to what is achievable with the classical FFTs when the field size $q$ is special. For several problems, this yields the asymptotically smallest known arithmetic circuits even in the standard monomial representation of polynomials.

The efficiency of the classical FFT follows from using the 2-to-1 squaring map to reduce the evaluation set of roots of unity of order $2^k$ to similar groups of size $2^{k?i}$, $i > 0$. Our algorithms operate similarly, using isogenies of elliptic curves with kernel size 2 as 2-to-1 maps to reduce $L$ of size $2^k$ to sets of size $2^{k?i}$ that are, like $L$, suitably related to elliptic curves, albeit different ones.