# zbMATH — the first resource for mathematics

Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology. (English) Zbl 1066.14024
J. Ramanujan Math. Soc. 16, No. 4, 323-338 (2001); errata ibid. 18, No. 4, 417-418 (2003).
Summary: We descrihe an algorithm for counting points on an arbitrary hyperelliptic curve over a finite field $$\mathbb{F}_{p^n}$$ of odd characteristic using Monsky-Washnitzer cohomology to compute a $$p$$-adic approximation to the characteristic polynomial of Frobenius. For fixed $$p$$, the asymptotic running time for a curve of genus $$g$$ over $$\mathbb{F}_{p^n}$$ with a rational Weierstrass point is $$O(g^{4+\varepsilon} n^{3+\varepsilon})$$.

##### MSC:
 14G05 Rational points 11G20 Curves over finite and local fields 14F43 Other algebro-geometric (co)homologies (e.g., intersection, equivariant, Lawson, Deligne (co)homologies) 14G15 Finite ground fields in algebraic geometry 14H25 Arithmetic ground fields for curves
Full Text: