Paper 2002/105 Original: eprint.iacr.org/2002/105 ↗
An Extension of Kedlaya's Algorithm to Hyperelliptic Curves in Characteristic 2
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.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2002-09-06: last updated
- 2002-08-02: published
- Short URL
- https://ia.cr/2002/105
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}