Paper 2006/240

Computing Zeta Functions of Nondegenerate Curves

W. Castryck, 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.

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

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Accepted for publication in International Mathematical Research Notices
Keywords
nondegenerate curveszeta functionMonsky-Washnitzer cohomologyKedlaya's algorithm
Contact author(s)
frederik vercauteren @ esat kuleuven be
History
2007-01-10: last of 2 revisions
2006-07-14: received
See all versions
Short URL
https://ia.cr/2006/240
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/240,
      author = {W.  Castryck and J.  Denef and F.  Vercauteren},
      title = {Computing Zeta Functions of Nondegenerate Curves},
      howpublished = {Cryptology ePrint Archive, Paper 2006/240},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/240}},
      url = {https://eprint.iacr.org/2006/240}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.