Proc. Lond. Math. Soc. 111 (2015), no. 6, 1379–1401 (DOI).
arXiv preprint (September 2015).
We present new algorithms for computing zeta functions of algebraic varieties over finite fields. In particular, let X be an arithmetic scheme (scheme of finite type over Z), and for a prime p let ζXp(s) be the local factor of its zeta function. We present an algorithm that computes ζXp(s) for a single prime p in time p1/2+o(1), and another algorithm that computes ζXp(s) for all primes p < N in time N (log N)3+o(1). These generalise previous results of the author from hyperelliptic curves to completely arbitrary varieties.