Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > DAVID LEVIT:
All reports by Author David Levit:

TR21-103 | 18th July 2021
Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, David Levit

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

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 ... more >>>




ISSN 1433-8092 | Imprint