Cryptology ePrint Archive: Report 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.

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)

Short URL: ia.cr/2002/105

Discussion forum: Show discussion | Start new discussion