Counting points on \(C_{ab}\) curves using Monsky-Washnitzer cohomology (Q814764)

In this article, the authors describe an algorithm to compute the zeta function of any \(C_{ab}\)-curve over a finite field \(\mathbb{F}_{p^n}\). It is a generalization of Kedlaya's algorithm for hyperelliptic curves, and so find a \(p\)-adic approximation of the characteristic polynomial of Frobenius by computing in the Monsky-Washnitzer cohomology of the curve. The technique to lift the Frobenius endomorphism is different from [J. Cryptology 19, No. 1, 1--25 (2006; Zbl 1100.14017)] and can be applied to any non-singular affine curve. Furthermore the method used to prove a tight bound on the convergence rate of the resulting power series remains also valid. Only the explicit description of a basis of the first Monsky-Walshnitzer cohomology group and the reduction formulae to express a differential on this basis are limited to \(C_{ab}\) curves. For fixed \(p\) the asymptotic running time for \(C_{ab}\) curves of genus \(g\) over \(\mathbb{F}_{p^n}\) is \(O(g^{5+\varepsilon} n^{3+\varepsilon})\) and the space complexity is \(O(g^3 n^3)\). For instance the order of a \(168\)-bit Jacobian of a \(C_{3,4}\) curve can be computed in \(1.4\) h.