Finite Fields and Their Applications vol:12 issue:1 pages:78-102
We describe an algorithm to compute the zeta function of any Cab curve over any finite field F-p(n). The algorithm computes a p-adic approximation of the characteristic polynomial of Frobenius by computing in the Monsky-Washnitzer cohomology of the curve and thus generalizes Kedlaya's algorithm for hyperelliptic curves. For fixed p the asymptotic running time for a C-ab curve of genus g over F-p(n) is O(g(5+epsilon)n(3+epsilon)) and the space complexity is O(g(3)n(3)). (c) 2005 Elsevier Inc. All rights reserved.