You are looking at a specific version 20020906:101526 of this paper. See the latest version.

Paper 2002/105

An Extension of Kedlaya's Algorithm to Hyperelliptic Curves in Characteristic 2

Jan Denef and Frederik Vercauteren

Abstract

We present an algorithm for computing the zeta function of an arbitrary hyperelliptic curve over a finite field $\FF_q$ of characteristic 2, thereby extending the algorithm of Kedlaya for odd characteristic. For a genus $g$ hyperelliptic curve defined over $\FF_{2^n}$, the average-case time complexity is $O(g^{4 + \varepsilon} n^{3 + \varepsilon})$ and the average-case space complexity is $O(g^{3} n^{3})$, whereas the worst-case time and space complexities are $O(g^{5 + \varepsilon} n^{3 + \varepsilon})$ and $O(g^{4} n^{3})$ respectively.

Note: Added more comments and cleaned up some proofs.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. A more down to earth version (i.e. without theory) will be published in the proceedings of CRYPTO 2002
Keywords
Hyperelliptic curvescryptographyKedlaya's algorithmMonsky-Washnitzer cohomology
Contact author(s)
frederik @ cs bris ac uk
History
2002-09-06: last of 2 revisions
2002-08-02: received
See all versions
Short URL
https://ia.cr/2002/105
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.