Counting Points on Hyperelliptic Curves using Monsky-Washnitzer Cohomology

By Kiran S. Kedlaya. 2001

272 citations recorded by the source corpus.

We describe an algorithm for counting points on an arbitrary hyperelliptic curve over a finite field 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 the field of p^n elements is O(g^{4+\epsilon} n^{3+\epsilon}).

Subfields: Computational Mechanics, Computational Theory and Mathematics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/024b0a21daeed17569ef540feced346b63a99a73

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Geometry and Topology

Citations in the corpus

Bounding Picard numbers of surfaces using p-adic cohomology (2006, methodology): “Here is the result; in its relevance to computing p -adic cohomology, it should be viewed as a generalization of [26, Lemma 2].”
A quasi quadratic time algorithm for hyperelliptic curve point counting (2006, methodology): “These methods rely on either Monsky-Washnitzer cohomology as described in [ Ked01 ] and [DV02] or on Dwork cohomology as in [Lau04a,LW04,Lau04b,LW02].”
Fourier transforms and $p$-adic ‘Weil II’ (2002, background): “(Accordingly, it too has been used recently to give explicit algorithms for computing zeta functions; see [ Ke1 ].) However, for a long time a proof of finite dimensionality of cohomology was lacking except for curves [Mn3], limiting the usefulness of the theory.”
Counting points on varieties over finite fields of small characteristic (2006, result): “We note that recently a similar result for special classes of plane curves was independently obtained in [8, 10], using Monsky-Washnitzer’s method.”
Deformation Theory and The Computation of Zeta Functions (2004, methodology): “The paper [17] also contains important improvements for elliptic curves, and [23, 26, 29] make signi-cant algorithmic advances.”
Guide to Elliptic Curve Cryptography (2004, methodology): “Another noteworthy algorithm is that of Kedlaya [240] for counting the points on hyperelliptic curves (of any genus) over finite fields of small odd characteristic.”