Counting points on hyperelliptic curves in average polynomial time

Ann. of Math. (2) 179 (2014), no. 2, 783–803 (DOI).

arXiv preprint (September 2013).


Let g ≥ 1 and let QZ[x] be a monic, squarefree polynomial of degree 2g + 1. For an odd prime p not dividing the discriminant of Q, let Zp(T) denote the zeta function of the hyperelliptic curve of genus g over the finite field Fp obtained by reducing the coefficients of the equation y2 = Q(x) modulo p. We present an explicit deterministic algorithm that given as input Q and a positive integer N, computes Zp(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.

Back to the main page