**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.

**Category / Keywords: **public-key cryptography / Hyperelliptic curves, cryptography, Kedlaya's algorithm, Monsky-Washnitzer cohomology

**Publication Info: **A more down to earth version (i.e. without theory) will be published in the proceedings of CRYPTO 2002

**Date: **received 30 Jul 2002, last revised 6 Sep 2002

**Contact author: **frederik at cs bris ac uk

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Note: **Added more comments and cleaned up some proofs.

**Version: **20020906:101526 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]