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
-
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},
url = {https://eprint.iacr.org/2006/240}
}