Let $k,pin mathbb{N}$ with $p$ prime and let $finmathbb{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_iinmathbb{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 $(dklog p)^{O(1)}sqrt{p}$, and admits a quantum version for smooth curves working in time $(dlog 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.
تحميل البحث