Foundations of Computational Mathematics vol:8 issue:1 pages:137-169
Let E_Gamma be a family of hyperelliptic curves defined by Y^2 = Q(X,Gamma) where Q is defined over a small finite field of odd characteristic. Then with gamma in an extension degree n field over this small field, we present a deterministic algorithm for computing the zeta function of the curve E_gamma by using Dwork deformation in rigid cohomology. The time complexity of the algorithm is O(n^2.667) and it needs O(n^2.5) bits of memory. A slight adaptation requires only O(n^2) space, but costs time O(n^3). An implementation of this last result turns out to be quite efficient for n big enough.