# Multi-point evaluations of a polynomial mod p

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

• Welcome to CS.SE! 1. How many values of $x$? The best algorithm will likely depend on that. 2. What do you mean by "best"? Are you looking for something with the best asymptotic running time? A practical solution? Something that is easiest to implement? – D.W. Jul 3 '16 at 2:21
• Doing the CodeChef contest problem codechef.com/JULY16/problems/POLYEVAL? Please don't ask us to solve your coding contest problem for you. If you're going to use material/problems from another source, you must credit/attribute the source. (Also, CodeChef prohibits from asking others to help you solve your problem; many consider asking us to tell you how to solve the contest problem to be cheating.) – D.W. Jul 11 '16 at 17:39
• @D.W. with some search it's easy to find the concept behind it, what's difficult is the implementation! Thanks by the way for not spilling the beans before the contest. – Sahil Arora Jul 11 '16 at 20:57

## 1 Answer

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.

• I feel like the chapter "multi-point polynomial evaluation" describes the basic idea for a general evaluation algorithm using FFT, with runtime O(n log^2 n): dis.uniroma1.it/~sankowski/lecture4.pdf Not sure if it applicable to DFT as well. – Niklas B. Jul 11 '16 at 9:13
• Thanks, NiklasB.! I've updated my answer based on that information. – D.W. Mar 6 at 21:32