# The IV AMMCS International Conference

## Waterloo, Ontario, Canada | August 20-25, 2017

# AMMSCS 2017 Plenary Talk

## Computing Zeta Functions in Average Polynomial Time

### Andrew Sutherland (MIT)

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.

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.

Andrew Sutherland received his undergraduate degree in
mathematics from MIT in 1990. Following a successful career as
an entrepreneur in the software industry, he returned to MIT and
completed his Ph.D. in 2007, winning the George M. Sprowles
Prize for his thesis on order computations in generic groups.
Sutherland is currently a Principal Research Scientist at MIT
with a research focus in computational number theory and was
recently awarded the Selfridge Prize for his work in this area.
He has played a leading role in a number of large scale
collaborations in open mathematics, including the polymath
project on prime gaps and the L-functions and Modular Forms
Database (LMFDB), and he serves on the editorial board of
several journals, including Mathematics of Computation.