2021/07/18 by Eli Ben‐Sasson, Dan Carmon, Ben-Sasson, Eli +5
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #Coding theory and cryptography #Cryptography and Residue Arithmetic #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2107.08473
openalex publication_date 2021/07/18 · openalex created_date 2021/08/02 · openalex updated_date 2026/07/28
For smooth finite fields Fq (i.e., when q-1 factors into small primes)\nthe Fast Fourier Transform (FFT) leads to the fastest known algebraic\nalgorithms for many basic polynomial operations, such as multiplication,\ndivision, interpolation and multi-point evaluation. However, the same\noperations over fields with no smooth order root of unity suffer from an\nasymptotic slowdown. The classical algorithm of Schonhage and Strassen incurred\na multiplicative slowdown factor of \log \log n on top of the smooth case.\nRecent remarkable results of Harvey, van der Hoeven and Lecerf dramatically\nreduced this multiplicative overhead to \exp(\log^* (n)).\n We introduce a new approach to fast algorithms for polynomial operations over\nall large finite fields. The key idea is to replace the group of roots of unity\nwith a set of points L \⊂ F suitably related to a well-chosen elliptic\ncurve group (the set L itself is not a group). The key advantage of this\napproach is that elliptic curve groups can be of any size in the Hasse-Weil\ninterval [q+1 \± 2\√(q)] and thus can have subgroups of large, smooth\norder, which an FFT-like divide and conquer algorithm can exploit. Compare this\nwith multiplicative subgroups over whose order must divide q-1.\n For polynomials represented by their evaluation over subsets of L, we show\nthat multiplication, division, degree-computation, interpolation, evaluation\nand Reed-Solomon encoding (also known as low-degree extension) with fixed\nevaluation points can all be computed with arithmetic circuits of size similar\nto what is achievable with the classical FFTs when the field size is special.\nFor several problems, this yields the asymptotically smallest known arithmetic\ncircuits even in the standard monomial representation of polynomials.\n