An extension of Kedlaya's algorithm to hyperelliptic curves in characteristic \(2\) (Q2499264)

The authors present an extension of Kedlaya's algorithm to compute the zeta function of an arbitrary hyperelliptic curve over a finite field of characteristic \(2\). The main difference with Kedlaya's algorithm is that the hyperelliptic curve can no longer be lifted arbitrarily to a \(2\)-adic ring; instead, a very specific lift is needed to ensure that the algebraic de Rham cohomology and the Monsky-Washnitzer cohomology are isomorphic. For a genus \(g\) hyperelliptic curve defined over the finite field with \(2^n\) elements, the average-case time complexity is \(O(g^{4+\varepsilon}n^{3+\varepsilon})\) and the average-case space complexity is \(O(g^3n^3)\), whereas the worst-case time and space complexities are \(O(g^{5+\varepsilon}n^{3+\varepsilon})\) and \(O(g^4n^3)\), respectively. An implementation in the C programming language shows that the cryptographic sizes are now feasible for any genus \(g\). For instance, computing the order of a \(160\)-bit Jacobian of a hyperelliptic curve of genus \(2,3,\) or \(4\) takes about \(75\) seconds. Several examples are given of hyperelliptic curves with these genera such that the group order of the Jacobian is divisible by a large prime number.