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

We present an algorithm to compute the zeta function of an arbitrary hyperelliptic curve over a finite field F_q of characteristic 2, thereby extending the algorithm of Kedlaya for odd characteristic. Given a genus g hyperelliptic curve defined over F_q ⁿ, the average-case time complexity is O(g^{4 + ε} n^{3 + ε}) and the average-case space complexity is O(g³ n³), whereas the worst-case time and space complexities are O(g^{5 + ε} n^{3 + ε}) and O(g⁴ n³), respectively.

Authors and Affiliations

1. Department of Mathematics, University of Leuven, Celestijnenlaan 200B, B-3001 Leuven-Heverlee, Belgium

   Jan Denef

2. Department of Electrical Engineering, University of Leuven, Kasteelpark Arenberg 10, B-3001 Leuven-Heverlee, Belgium and Computer Science Department, University of Bristol, Woodland Road, Bristol BS8 1UB, England

   Frederik Vercauteren

Corresponding authors

Correspondence to Jan Denef or Frederik Vercauteren.

Reprints and permissions