## Cryptology ePrint Archive: Report 2006/240

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

[ Cryptology ePrint archive ]