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}$?

  • 1
    $\begingroup$ 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. $\endgroup$
    – user16034
    Commented May 2, 2023 at 21:34
  • $\begingroup$ @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))$ ? $\endgroup$ Commented May 2, 2023 at 22:33
  • 1
    $\begingroup$ 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. $\endgroup$
    – user16034
    Commented May 3, 2023 at 7:03
  • 1
    $\begingroup$ If $n$ and $\deg(f)$ are moderate, one can wonder if this "optimization" is worth the effort. $\endgroup$
    – user16034
    Commented May 3, 2023 at 7:14
  • $\begingroup$ @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? $\endgroup$ Commented May 3, 2023 at 19:03


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.