CryptoDB
An Extension of Kedlaya's Algorithm to Hyperelliptic Curves in Characteristic 2
Authors: | |
---|---|
Download: | |
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. |
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 }