# Algorithm to compute sum of quotient polynomials

Let $$f(X)$$ be a polynomial in $$\mathbb{F}_p[X]$$ for some prime $$p$$ (of size 256 bits) that is not necessarily FFT-friendly. Let $$a_1,\cdots,a_n$$, $$b_1,\cdots, b_n$$ be $$\mathbb{F}_p$$ elements.

What is the most efficient algorithm to compute the polynomial $$h(X):= \sum\limits_{i=1}^n b_i\cdot \frac{f(X)-f(a_i)}{X-a_i}$$?

• The straight way is by computing all coefficients of the fractions (by Horner's rule) and taking the linear combinations. This takes $O(n\deg(f))$ operations. There is some hope for a faster solution because the expression can be written as the product of a Vandermonde matrix, a Hankel matrix and a vector, where an FFT can be used.
– user16034
Commented May 2, 2023 at 21:34
• @YvesDaoust Thanks for your response. Will think along the lines you suggested. In the absence of smooth order roots of unity in $\mathbb{F}_p$, would a $O(N \cdot\log(N) \cdot\log(\log(N)))$ be feasible, where $N = max(n, deg(f))$ ? Commented May 2, 2023 at 22:33
• Sorry, I wrote FFT, but the truth is DFT. The cost would be $O(D(n)+D(\deg(f)))$, where $D(n)$ is the cost of a DFT, whatever that is in your case.
– user16034
Commented May 3, 2023 at 7:03
• If $n$ and $\deg(f)$ are moderate, one can wonder if this "optimization" is worth the effort.
– user16034
Commented May 3, 2023 at 7:14
• @YvesDaoust The use case has $\deg(f)$ in the low thousands and $n$ substantially larger (in the millions). I assume the optimization - if possible - might be worth the effort given the parameters? Commented May 3, 2023 at 19:03