Computing zeta functions of nondegenerate curves

Abstract. In this paper we present a p-adic algorithm to compute the zeta function of a nondegenerate curve over a finite field using Monsky-Washnitzer cohomology. The paper vastly generalizes previous work since in practice all known cases, e.g. hyperelliptic, superelliptic and Cab curves, can be transformed to fit the nondegenerate case. For curves with a fixed Newton polytope, the property of being nondegenerate is generic, so that the algorithm works for almost all curves with given Newton polytope. For a genus g curve over Fpn, the expected running time is e O(n 3 g 6 + n 2 g 6.5), whereas the space complexity amounts to e O(n 3 g 4), assuming p is fixed. Keywords: nondegenerate curves, zeta function, Monsky-Washnitzer cohomology, Kedlaya’s algorithm, Newton polytope, toric geometry, effective Nullstellensatz