  Let $k,p\in \mathbb{N}$ with $p$ prime and let $f\in\mathbb{Z}[x_1,x_2]$ be a
bivariate polynomial with degree $d$ and all coefficients of absolute value at
most $p^k$. Suppose also that $f$ is variable separated, i.e., $f=g_1+g_2$ for
$g_i\in\mathbb{Z}[x_i]$. We give the first algorithm, with complexity
sub-linear in $p$, to count the number of roots of $f$ over $\mathbb{Z}$ mod
$p^k$ for arbitrary $k$: Our Las Vegas randomized algorithm works in time
$(dk\log p)^{O(1)}\sqrt{p}$, and admits a quantum version for smooth curves
working in time $(d\log p)^{O(1)}k$. Save for some subtleties concerning
non-isolated singularities, our techniques generalize to counting roots of
polynomials in $\mathbb{Z}[x_1,\ldots,x_n]$ over $\mathbb{Z}$ mod $p^k$.
  Our techniques are a first step toward efficient point counting for varieties
over Galois rings (which is relevant to error correcting codes over
higher-dimensional varieties), and also imply new speed-ups for computing Igusa
zeta functions of curves. The latter zeta functions are fundamental in
arithmetic geometry.
