*Note: Originally asked on Math StackExchange here, 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 *distinct* 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*}

Initially, $R(x) = N'(x)$. Furthermore, the dividend $R$ has degree $\le 2n-1$ while the divisor has degree $n$. Initially $n = k/2$, 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 "reversal-based" 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. (There is also a "reciprocal-based" algorithm described in Chapter 8.3 of "The Design and Analysis of Computer Algorithms," but I suspect this is slower.)

**Is there any way to speed up this reversal-based 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 an $\ell$th root of unity ($\ell > k$) but
**not necessarily**the $i$th one (or $i-c$th one) - $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), in Sec 7.5, pg 194.