  Let g >= 1 and let Q be a monic, squarefree polynomial of degree 2g + 1 in
Z[x]. 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
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.

Number Theory