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

Multipoint evaluation is the computational task of evaluating a polynomial given as a list of coefficients at a given set of inputs. Besides being a natural and fundamental question in computer algebra on its own, fast algorithms for this problem is also closely related to fast algorithms for other natural ... more >>>