Counting points on varieties over finite fields of small characteristic

Abstract

We present a deterministic polynomial time algorithm for computing the zeta function of an arbitrary variety of fixed dimension over a finite field of small characteristic. One consequence of this result is an efficient method for computing the order of the group of rational points on the Jacobian of a smooth geometrically connected projective curve over a finite field of small characteristic.

To appear in: "Algorithmic number theory: lattices, number fields, curves and cryptography", J.P. Buhler and P. Stevenhagen (ed.), Math. Sci. Res. Inst. Publ. 44. (Submitted July 2001; Accepted October 2002.)