Pt.3 Counting points on curves over finite fields | David Harvey, University of New South Wales
Channel: IAS | Park City Mathematics Institute | PCMI
Date: 04/08/2022

Lecture 3–Counting points on curves over finite fields 
The zeta function of an algebraic variety over a finite field is a rational function that encodes a wealth of interesting arithmetic information about the variety. Concretely, computing the zeta function amounts to counting the number of solutions to a system of polynomial equations in several variables. In this course, I will discuss a few algorithms for computing zeta functions, focusing in particular on the case of hyperelliptic curves, i.e., equations of the form $y^2 = f(x)$. The first main goal of the course is to explain an algorithm that computes the zeta function of a curve over a field of characteristic $p$ in time roughly $p^{1/2}$. The second main goal is to explain an algorithm that takes as input a curve defined over $\mathbb{Z}$, and computes the zeta function of its reduction modulo $p$ simultaneously for all (good) primes $p angledbracket N$ in time roughly $N (\log N)^3$, i.e., in ``average polynomial time'' per prime. Some familiarity with thinking about algorithms and asymptotic complexity will probably be helpful for this course, but I will not assume any prior experience with zeta functions or algorithms for computing them.

https://www.ias.edu/pcmi/2022-graduate-summer-school-course-descriptions