Motivation
The motivation behind this question is from a computational mathematics and combinatorics background. It is often convenient to express a problem as a product of polynomials so that the coefficients represent various counts. As example, counting change possible from 3 pennies, 2 nickles, and a dime: $\left(x^0 + x^1 + x^2 + x^3\right)\left(x^0 + x^5 + x^{10}\right)\left(x^0 + x^{10}\right)$, which when expanded the coefficients tell us how many distinct ways each sum can be made.
Expanding such a polynomial can be expensive, the fast fourier transform lets us multiply two polynomials of degree $d$ in $O\left(d\log{d}\right)$ time, and multiply $k$ linear terms in $O\left(k \log^2 k\right)$ time, but this can still be overly expensive when the degrees of the individual terms are large. In the event that terms we want are powers of $x^k$, we can evaluate our polynomial $P(x)$ at powers of a k-th primitive root of unity, sum the results and divide by k. We can also multiply $P(x)$ by a factor of $x^a$ to enable this trick in some cases. For small $k$ this extremely efficient, since it only requires k evaluations of $P(x)$, which itself can be optimized by exploiting symmetry in the roots of unity.
As an example, consider we want to know how many distinct combinations of 5 books have an even number of total pages: $P(x) = \left(1 + x^{503}\right)\left(1 + x^{313}\right)\left(1 + x^{761}\right)\left(1 + x^{244}\right)\left(1 + x^{606}\right)$, get our primitive 2nd root in $\mathbb{C}$, which is just $-1$, sum over its powers up to $1$, and divide by 2: $\frac{P(-1) + P(1)}{2} = 16$. Note how the evaluation takes much less work than fully expanding either naively or by the FFT, due to the exponential growth with respect to the number of terms and the linear growth with respect to the order, respectively.
Problem
For all other cases however, we are forced to expand the full polynomial and then cherry pick the coefficients we want. In the case where the polynomial is a generating function, that isn't even an option since it has infinitely many terms. If we had a way of "filtering" all terms of degree greater than k from our evaluation of $P(x)$, we'd be able to quickly obtain any individual coefficient, or aggregate ranges of coefficients, by simply taking a difference between two evaluations. This is my question at its core. Can we somehow evaluate $Q(x) = P(x) \bmod x^k$ at some value $m$, by only evaluating $P(x)$ at some few carefully chosen points?
What I've Tried
I know $d+1$ points uniquely define a degree $d$ polynomial, so that sets an upper bound since at that point we could just reconstruct the entire polynomial $P(x)$, but I'm hoping for something that's proportional to k, up to some logarithmic factors.
I'm aware that I could choose sufficiently large $m$ and evaluate $P(m) \bmod m^k$, and the smallest non-negative residue of that residue class will exactly equal $Q(m)$ if $Q(m)$ is non-negative, else the largest negative residue will equal it. Doing this for several values will give me a system of k equations that I can solve for the coefficients. The problem with this approach, apart from needing to know the signs of $Q(m)$, is that the integers involved can be huge- far larger than the already potentially large coefficients. This would mean $O\left(k \log(k) \log(\log(k))\right)$ time for each integer multiplication. This is probably still viable for extremely small k, but its not a good general solution.
In a similar spirit, I've also looked into operating in the ring $\mathbb{Z}/p^k\mathbb{Z}$, evaluating at $p\alpha^j$, where $\alpha^{\left(p-1\right)p^{k-1}} \equiv 1 \bmod p^k$, causing higher order terms to vanish, but utilizing the symmetry to optimize evaluation. The problem is the same however, the terms are of integers in range of $p^k$.
I've looked through the literature for polynomial division algorithms, but everything (understandably) seems to work under the premise that you already have the coefficients of the polynomial you wish to divide. Additionally, I don't have a strong abstract algebra background, being a computer scientist who self-taught mathematics, which makes it difficult to reason through some of them.
Admittedly, I'm a bit out of my depths here. Its possible there's a simple answer that I'm completely overlooking. Any insights are appreciated.
