# Can we evaluate a polynomial of degree N modulo M at all M points, faster than Θ(mn) time?

Given a polynomial $P(x)$ of degree $N$, evaluate $P(x) \bmod M$ at $x = 0$ to $M-1$, where $M$ is a prime number of order $10^6$. Can we do any better than $O(NM)$ given the constraints we only need the value $P(x) \bmod M$?

• Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. – Raphael Jul 6 '16 at 13:13
• Note that "better than O(NM)" is a nonsensical phrase. I guess you mean o(NM), whatever that means precisely with two variables. – Raphael Jul 6 '16 at 22:21
• 1. What's the source for this problem? In what context did you run across it? 2. What research have you done? Have you looked on Wikipedia and in standard textbooks? Did you search for related questions here? We expect you to do a significant amount of research before asking, and to show us in the question what research you've done. A quick search on this site immediately turns up cs.stackexchange.com/q/60239/755, which looks highly relevant. – D.W. Jul 6 '16 at 22:54
• Taken from a live programming contest: codechef.com/JULY16/problems/POLYEVAL – D.W. Jul 11 '16 at 17:41

Given a primitive root g of M, it is possible to evaluate $P (g^0), P (g^1), \ldots, P (g^{M-1})$ in $O (\max (N, M) \log \max (N, M))$ steps, and then you just rearrange the resulting values and add $P (0)$ which is just the constant coefficient of the polynomial $P$.
Thanks D.W. for the link. The answer given there says that for an arbitrary set of points evaluating all the polynomial values faster than $N$ times number of points can't be done, but of course the result above is useful whenever the number of points is substantially more than $N \log N$.