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
-
CC BY
BibTeX
@misc{cryptoeprint:2002/105,
author = {Jan Denef and Frederik Vercauteren},
title = {An Extension of Kedlaya's Algorithm to Hyperelliptic Curves in Characteristic 2},
howpublished = {Cryptology {ePrint} Archive, Paper 2002/105},
year = {2002},
url = {https://eprint.iacr.org/2002/105}
}
