Computing zeta functions of Artin-Schreier curves over finite fields II

We describe a method which may be used to compute the zeta function of an arbitrary Artin-Schreier cover of the projective line over a finite field. Specifically, for covers defined by equations of the form Zp - Z = f (X) we present, and give the complexity analysis of, an algorithm for the case in which f (X) is a rational function whose poles all have order 1. However, we only prove the correctness of this algorithm when the field characteristic is at least 5. The algorithm is based upon a cohomological formula for the L-function of an additive character sum. One consequence is a practical method of finding the order of the group of rational points on the Jacobian of a hyperelliptic curve in characteristic 2. © 2003 Elsevier Inc. All rights reserved.