International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Computing Zeta Functions of Nondegenerate Curves

Authors:
W. Castryck
J. Denef
F. Vercauteren
Download:
URL: http://eprint.iacr.org/2006/240
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2006-21733,
  title={Computing Zeta Functions of Nondegenerate Curves},
  booktitle={IACR Eprint archive},
  keywords={foundations / nondegenerate curves, zeta function, Monsky-Washnitzer cohomology, Kedlaya's algorithm},
  url={http://eprint.iacr.org/2006/240},
  note={Accepted for publication in International Mathematical Research Notices frederik.vercauteren@esat.kuleuven.be 13523 received 13 Jul 2006, last revised 9 Jan 2007},
  author={W. Castryck and J. Denef and F. Vercauteren},
  year=2006
}