*Note: Originally asked on Math StackExchange [here](https://math.stackexchange.com/questions/2731767/computing-remainders-modulo-prod-i-in-s-x-x-i-fast-using-fft), without an answer. Figured I should try here, since this is a more research-level question.*

I am trying to implement a fast polynomial *multipoint evaluation* algorithm via FFT (e.g., the one described in Chapter 10.1 of "Modern Computer Algebra," 3rd edition).
I should mention that the polyonomial being evaluated is the formal derivative $N'(x)$ of: $$N(x) = (x-x_1)(x-x_2)\cdots(x-x_k)$$

Specifically, we're evaluating $N'(x)$ at points $x_1, x_2, \dots, x_k$, where $k$ is a power of two.

I'm looking for *any mathematical tricks* that will lead to *practical* improvements in the multipoint evaluation algorithm.
AFAICT, the main bottleneck will be computing remainders after division by $(x - x_i)\cdots(x-x_j)$.

As a refresher, at any "node" in the multipoint evaluation tree, we have a subset of points $x_i, \dots, x_j, x_{j+1}, \dots, x_\ell$, a previous remainder $R(\cdot)$, and we want to compute:
\begin{align*}
R(x) &\bmod (x - x_i)\cdots(x-x_j)\\
R(x) &\bmod (x - x_{j+1})\cdots(x-x_\ell)
\end{align*}
Furthermore, the dividend $R$ has degree $\le 2n-1$ while the divisor has degree $n$.
Initially $n = k$, so it's a power of two, and then $n$ gets halved as we go down the multipoint evaluation tree.

I am aware there is a $O(n\log{n})$ algorithm based on FFT for computing remainders.
For example, the algorithm described in Chapter 9.1 of "Modern Computer Algebra," 3rd edition first computes the quotient by computing a modular inverse and then computes the remainder.

**Is there any way to speed up this division algorithm** given our particular setting:

 - We do not need the quotient, only the remainder.
 - We only need to divide by $(x - x_i)\cdots(x-x_j)$, for some $i,j$ where $1 \le i,j \le k$.
 - $x_i$ can be the $(i-1)$th $k$th root of unity
 - $k$ is a power of two or can be adjusted as needed
 - We're doing a multipoint evaluation on $N'(x)$

The only mathematical trick I could find was in Todd Mateer's *"Fast Fourier Transform Algorithms with Applications"* PhD thesis ([pdf](https://tigerprints.clemson.edu/all_dissertations/231/)), in Sec 7.5, pg 194.