*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.