Let $p$ be a prime number and 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 evaluation 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 evaluation consists in computing the values $$y_1 = P(x_1), y_2 = P(x_2), \dots, y_{n} = P(x_{n}),$$ 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)$.
- There exists faster algorithms for the case that the polynomial $P(x)$ is binary?
- If not, there exists some trick to improve efficiency for this case?
