## CryptoDB

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

Authors: Jan Denef Frederik Vercauteren URL: http://eprint.iacr.org/2002/105 Search ePrint Search Google 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.
##### BibTeX
@misc{eprint-2002-11628,
title={An Extension of Kedlaya's Algorithm to Hyperelliptic Curves in Characteristic 2},
booktitle={IACR Eprint archive},
keywords={public-key cryptography / Hyperelliptic curves, cryptography, Kedlaya's algorithm, Monsky-Washnitzer cohomology},
url={http://eprint.iacr.org/2002/105},
note={A more down to earth version (i.e. without theory) will be published in the proceedings of CRYPTO 2002 frederik@cs.bris.ac.uk 11936 received 30 Jul 2002, last revised 6 Sep 2002},
author={Jan Denef and Frederik Vercauteren},
year=2002
}