Counting points on hyperelliptic curves in average polynomial time
David Harvey · Annals of Mathematics · 2014
Let g ≥ 1, and let Q ∈ Z[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 y 2 = 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. For my wife, Lara