Let $ X $ be a smooth projective curve defined over a finite field of prime order $ p $. Determining the number of rational points on $ X $, or more generally, computing the zeta function of $ X $, is a core problem in computational number theory with many applications. For curves of genus $ g = 1 $, Schoof uses a CRT approach to obtain a polynomial-time algorithm; Schoof's algorithm has been generalized to curves of higher genus by Pila, with a running time that is polynomial in log $ p $ but exponential in $ g $. Alternatively, $ p $-adic approaches based on generalizations of Kedlaya's algorithm yield a running time that is polynomial in $ g $ but exponential in log $ p $. No algorithm with a running time that is polynomial in both $ g $ and log p is currently known.
Now suppose $ X $ is instead defined over the rational numbers, and consider the sequence of curves $ X_p $ obtained by taking the reductions of $ X $ modulo primes $ p $ of good reduction up to some bound $ N $. The problem of computing the zeta functions of all the $ X_p $ naturally arises when one wishes to compute the $ L $-function of $ X $, or to study its Sato-Tate distribution. Harvey has shown that this problem can be solved in time quasi-linear in $ N $; the average time to compute the zeta function of each of the curves $ X_p $ is polynomial in both $ g $ and log $ p $.
I will report on practical implementations of this algorithm, focusing in particular on curves of genus 3, both hyperelliptic and non-hyperelliptic, where we have recently obtained results that are dramatically faster than using either a CRT or $ p $-adic approach to compute the zeta function of each $ X_p $ individually.