ArXiv.org · 2001 · 208 citations · 5 references
Natural SciencesMathematicsAlgorithmsComputational GeometryTheory Of ComputationAlgebraic GeometryArithmetic GeometryElliptic CurvesCounting Rational PointsFinite Field ArithmeticP-adic Cohomology
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+ε} n^{3+ε}).
5
Robert T. Moenck · 1973 · 87 citations
Formal Cohomology: III. Fixed Point Theorems
Paul Monsky · Annals of Mathematics · 1971 · 55 citations
Formal Cohomology: II. The Cohomology Sequence of a Pair
Paul Monsky · Annals of Mathematics · 1968 · 47 citations