[Resource Topic] 2002/105: An Extension of Kedlaya's Algorithm to Hyperelliptic Curves in Characteristic 2

Welcome to the resource topic for 2002/105

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

Authors: Jan Denef, Frederik Vercauteren


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.

ePrint: https://eprint.iacr.org/2002/105

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .