Let $p(x) = a_0 + a_1x + a_2x^2 + \dots + a_{n-1}x^{n-1}$ be a polynomial in $\mathbb{Z}_p[x]$ with binary coefficients, i.e., such that $a_i \in \{0,1\}$ for all $i = 0,1,\dots,n-1$. I like to refer to this kind of polynomials them as binary polynomials.

The problem of interpolation is defined as follows: Given $x_1, x_2, \dots, x_{n} \in \mathbb{Z}_p$ and $a_0,a_1, \dots, a_{n-1}$, polynomial interpolation consists in computing the values $$y_1 = p(x_1), y_2 = p(x_2), \dots, y_{n} = p(x_{x}),$$ where $p(x)$ is the polynomial $p(x) = a_0 + a_1x + a_2x^2 + \dots + a_{n-1}x^{n-1}$.

I recently discovered the DFT algorithm (here, the values $x_i$ are taken to be the powers of a primitive $n$-th root of unity) to perform this task in $\mathcal{O}(n \log n)$.

  1. There exists faster algorithms for the case that the polynomial $p(x)$ is binary?
  2. If not, there exists some trick to improve efficiency for this case?


You must log in to answer this question.