Counting points on hyperelliptic curves in average polynomial time

Abstract

Let $g \geq 1$, and let $Q \in \mathbf{Z}[x]$ be a monic, squarefree polynomial of degree $2g + 1$. For an odd prime $p$ not dividing the discriminant of $Q$, let $Z_p(T)$ denote the zeta function of the hyperelliptic curve of genus $g$ over the finite field $\mathbf{F}_p$ obtained by reducing the coefficients of the equation $y^2 = Q(x)$ modulo $p$. We present an explicit deterministic algorithm that given as input $Q$ and a positive integer $N$, computes $Z_p(T)$ simultaneously for all such primes $p < N$, whose average complexity per prime is polynomial in $g$, $\log N$, and the number of bits required to represent $Q$.