# Counting points on hyperelliptic curves in average polynomial time

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

arXiv preprint (September 2013).

## Abstract

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

Back to the main page