If $f$ is a polynomial of degree $k$, can we quickly compute $f(1),f(2),\dots,f(n).$ $f(x)=\left(\sum_{i=1}^k{a_ix^i}\right) \pmod P$
$P > n \gg k.$
Obviously calculating $f(1),f(2)..f(n)$ takes $O(nk)$.
So is there a faster way to speed up the process? $k$ is not very big. $k$ is only about $30.$
 A: We are given
$$ f(x)=\left(\sum_{i=1}^k{a_ix^i}\right) \pmod P. $$
Since $\,f(x)\,$ is a polynomial mod $\,P\,$, then it is periodic.
That is, $\,f(x+P) = f(x) \pmod P.\,$ Thus, all you need to do
is compute $\,f(0),f(1),\dots,f(P-1)\,$ and there is no need for
any further computation of $\,f(n).\,$ Even though $\,P\,$ may be
big, it is a constant $\,O(1)\,$ compared to $\,O(nk).$
Of course, this is assuming that $\,P\,$ is fixed and that $\,n\,$
can be arbitrarily large. If $\,P\,$ depends on $\,n\,$ then that
is a very different situation. In that case, $\,P\,$ doesn't even matter.
Use a difference table up to $k$th order differences. Each new value
of $\,f(n)\,$ takes $\,k\,$ additions for time complexity of $\,O(nk)\,$
additions with no multiplications required. This is very fast in my opinion.
A: Thanks for your reply.In fact, both n and P are large, P>n, k is small.
I know how to use FFT to speed up multipoint evaluations of polynomials, it takes $O(nlog^2n)$.
Because k is small here, and x is 1,2,3...,n, so I guess there's a faster way to do it.
