International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Jan Denef
Frederik Vercauteren
Download:
URL: http://eprint.iacr.org/2002/105
Search ePrint
Search Google
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
}