**Computing Zeta Functions of Nondegenerate Curves**

*W. Castryck and J. Denef and F. Vercauteren *

**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 all known cases, e.g. 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 $\FF_{p^n}$, the expected running time is $\widetilde{O}(n^3 g^6 + n^2 g^{6.5})$, whereas the space complexity amounts to $\widetilde{O}(n^3 g^4)$, assuming $p$ is fixed.

**Category / Keywords: **foundations / nondegenerate curves, zeta function, Monsky-Washnitzer cohomology, Kedlaya's algorithm

**Publication Info: **Accepted for publication in International Mathematical Research Notices

**Date: **received 13 Jul 2006, last revised 9 Jan 2007

**Contact author: **frederik vercauteren at esat kuleuven be

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Note: **Some minor corrections to previous editions and link to errata of previous papers

**Version: **20070110:040021 (All versions of this report)

**Short URL: **ia.cr/2006/240

[ Cryptology ePrint archive ]