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})\).

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: arXiv