International Mathematics Research Papers vol:2006 pages:1-57
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, for example, hyperelliptic, superelliptic, and C-ab 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 F(p)n, the expected running time is (O) over tilde (n(3)g(6) + n(2)g(6.5)), whereas the space complexity amounts to (O) over tilde (n(3)g(4)), assuming p is fixed.