Hypothesis: All calculations and polynomials are defined over a finite field of prime order.
Assume we know all roots $r_i$ of a polynomial: $P(x)=(x-r_1)(x-r_2)...(x-r_n)$ and a set of x-coordinates: $\{x_1,,,x_n\}$.We want to evaluate P(x) at every $x_i$.
Question: What is the most efficient of computing $P(x_i)$ for every $x_i$?
We know that $P(x_i)=\prod^{n}_{j=1}(x_i-r_j)$ is a navive way of evaluating $P(x)$ at $x_i$.