Counting the number of points of an algebraic variety over a finite field, or equivalently computing its so called zeta function, is a central problem in computational number theory with applications to cryptography and coding theory. For elliptic curves and some curves of genus 2, variants of Schoof’s polynomial time algorithm can be used. For more general varieties, the best available algorithms are based on p-adic cohomology. Building on work of Kedlaya, Lauder and Harvey, over the past years we have obtained some of the best and most general algorithms of this type. The talk will give an overview of some of the recent work in this area and will be aimed at a rather general audience.
Algorithmic Number Theory, Coding and Cryptography
