Multi-point evaluations of a polynomial mod p

Question

Given a polynomial of degree $n$ modulo a prime number $p$, I want to evaluate that polynomial at multiple values of the variable $x$, what is the best way to do this?
I tried using Berlekamp's algorithm for factorization but it takes $O(n^3)$ just to factorize and then $O(n)$ per point evaluation. Is there any other way to bring the complexity down considerably like to $n\log(q)$ where $q$ is the number of points I want to evaluate the polynomial at? Or possibly polynomial time? All the coefficients and the values of $x$ that the polynomial is to be evaluated at lie between the $0$ and $prime - 1$, the prime is of order $10^6$.

Answer 1

No, $O(n \lg q)$ running time is not achievable. It takes $\Omega(q)$ space even just to write out the answer, so any algorithm will necessarily have running time at least $\Omega(q)$.

However, you can find algorithms that are more efficient than the naive solution. The naive solution for evaluating a polynomial of degree $n$ at $q$ points takes $O(nq)$ time, by using Horner's rule $q$ times. It turns out there are faster algorithms to do this, namely, in $O(\max(n,q) \log^2 \max(n,q))$ time. For simplicity of exposition, let me assume $q=n$, so the goal is to evaluate the polynomial $f(x)$ at points $x_1,\dots,x_n$.

We're going to use divide-and-conquer. Define

$$\begin{align*} f_0(x) &= f(x) \bmod (x-x_1)(x-x_2)\cdots(x-x_{n/2})\\ f_1(x) &= f(x) \bmod (x-x_{n/2+1})\cdots(x-x_n) \end{align*}$$

Now we have

$$f(x_i) = \begin{cases} f_0(x_i) &\text{if }i\le n/2\\ f_1(x_i) &\text{otherwise.}\end{cases}$$

Thus, it suffices to evaluate $f_0(x)$ at the points $x_1,\dots,x_{n/2}$ and evaluate $f_1(x)$ at the points $x_{n/2+1},\dots,x_n$. We can do this by a recursive invocation of the same procedure. Since both $f_0(x)$ and $f_1(x)$ have degree at most $n/2$, we're invoking the procedure recursively on two subproblems of size $n/2$.

This requires us compute $f_0(x)$ and $f_1(x)$ from $f(x)$. This can be done in $O(n \log n)$ time, using FFT-based polynomial division, which works similar to FFT-based polynomial multiplication (see here, here, and these slides).

The running time of this divide-and-conquer algorithm is

$$T(n) = 2 T(n/2) + O(n \log n),$$

which has the solution $T(n) = O(n \log^2 n)$. Thus, you can evaluate a polynomial of degree $n$ at $n$ arbitrary points in $O(n \log^2 n)$ time.

Since you are working modulo $p$, you want to use a Discrete Fourier Transform designed for mod $p$ arithmetic.

Thanks to Niklas B. for pointing me to http://www.dis.uniroma1.it/~sankowski/lecture4.pdf.