Fast evaluation of polynomials Let $x_1,\dots,x_n$ and $y_1,\dots,y_N$ be some known integers modulo $2^k$, where $n\ll N$.

For each $x_i$, I have the following polynomial:

$$P_i(z)= \prod_{j=0}^{k-1}(z+2^jx_i) \mod 2^k.$$

Note that these polynomials are sparse, because only high powers of $z$ survive the coefficient-wise reduction.

My objective is to find the values of $y_1,\dots,y_N$ that vanish each of these polynomials, i.e., find the zeroes among $P_i(y_j)$ for $i\leq n, j\leq N$.

The naive approach of (perform every evaluation) is obviously on $O(knN)$ products in this ring of integers. Is there any way to do better, considering the form of these polynomials and the fact that they are sparse?
I think you can find the pairs $(i,j)$ with $P_i(y_j)=0$ in time $N\cdot\log(N)$ for preprocessing and $k\cdot n\cdot\log(N)$ for processing, if you can use space $N$ for preprocessing the $y_i$:

Preprocessing consists of generating (1) the list $E$ of all $j$ such that $y_j$ is even, and (2) a tree (or something even faster) that you can query in time $\log(N)$ for a given $y$ to get the list of all $j$ such that $y=y_j$.

Now loop over all $x_i$, adding to the result either (1) all indices $(i, e)$ for $e\in E$ if $x_i$ is even or (2) all $(i, j)$ with $y_j = -x_i\cdot 2^l \bmod 2^k$ for some $l\le k$ (using the precomputed tree) if $x_i$ is odd.

The reason why this gives the correct result is written in my first comment to your question.