Counting points on algebraic curves over finite fields has numerous applications in communications and cryptology, and has led to some of the most beautiful results in 20th century arithmetic geometry. A natural generalization is to count the number of points over prime power rings, e.g., the integers modulo a prime power. However, the theory behind the latter kind of point counting began more recently and there are numerous gaps in our algorithmic knowledge.

We give a simple combinatorial construction that reduces point counting over prime power point counting to the prime field case. In particular, for any bivariate polynomial f in Z[x,y] and positive integers p and k with p prime, we show how one can count the number of roots of f in (Z/(p^k))^2 in time p^{1/2 + o(1)} (dk)^{O(1)}, and even faster for certain curves. This generalizes earlier results of Cheng, Lecerf, Saxena, and Wan in the univariate case, and simplifies earlier work of Denef, Igusa, and Veys on local zeta functions.

This is joint work with Caleb Robelle and Yuyu Zhu.