Author:

Keywords:

hyperelliptic curves, kedlaya's algorithm, monsky-washnitzer cohomology, formal cohomology, roots, cosic, Science & Technology, Technology, Computer Science, Theory & Methods, Computer Science, Kedlaya's algorithm, Monsky-Washnitzer cohomology, FORMAL COHOMOLOGY, ROOTS

Abstract:

We present an algorithm for computing the zeta function of an arbitrary hyperelliptic curve over a finite field F-q of characteristic 2, thereby extending the algorithm of Kedlaya for small odd characteristic. For a genus g hyperelliptic curve over F-2(n), the asymptotic running time of the algorithm is O(g(5+epsilon)n(3+epsilon)) and the space complexity is O(g(3)n(3)).