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 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), in Sec 7.5, pg 194.