Counting Points on Hyperelliptic Curves using Monsky-Washnitzer Cohomology

Abstract

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+ε}).

10 pages; v2: corrected runtime exponent, added explanation of Lefschetz trace formula, corrected typos

Cited by in corpus (50)

• Fast algorithms for computing isogenies between elliptic curves
• Counting points on varieties over finite fields of small characteristic
• Computing Hasse-Witt matrices of hyperelliptic curves in average polynomial time
• Computing Hasse-Witt matrices of hyperelliptic curves in average polynomial time, II
• Bounding Picard numbers of surfaces using p-adic cohomology
• Tracking p-adic precision
• Dévissages des F-complexes de D-modules arithmétiques en F-isocristaux surconvergents
• Sato-Tate groups of some weight 3 motives
• Kedlaya's algorithm in larger characteristic
• Moments of zeta functions associated to hyperelliptic curves over finite fields
• An introduction to motivic zeta functions of motives
• Explicit Coleman integration for hyperelliptic curves
• Families of hyperelliptic curves
• Explicit Coleman Integration in Larger Characteristic
• Efficient computation of p-adic heights
• Cohomology with closed support on the overconvergent site
• Fourier transforms and p-adic "Weil II"
• A p-adic quasi-quadratic point counting algorithm
• Point counting in families of hyperelliptic curves in characteristic 2
• Computing Zeta Functions of Nondegenerate Curves
• Resultants and subresultants of p-adic polynomials
• A recursive method for computing zeta functions of varieties
• Memory efficient hyperelliptic curve point counting
• Efficiently computable endomorphisms for hyperelliptic curves
• Point counting in families of hyperelliptic curves
• On p-adic Frobenius lifts and p-adic periods, from a Deformation Theory viewpoint
• Constructing elliptic curves in almost polynomial time
• On pairs of p-adic analogues of the conjectures of Birch and Swinnerton-Dyer
• Isogenies for point counting on genus two hyperelliptic curves with maximal real multiplication
• The functional equation for L-functions of hyperelliptic curves
• Sato-Tate groups of genus 2 curves
• Fast point counting on genus two curves in characteristic three
• Improvements to the deformation method for counting points on smooth projective hypersurfaces
• Frobenius lifts and point counting for smooth curves
• An extension of Kedlaya's algorithm for hyperelliptic curves
• Counting points on hyperelliptic curves in average polynomial time
• Explicit crystalline lattices in rigid cohomology
• A p-adic Height Function Of Cryptanalytic Significance
• Ranks of elliptic curves over function fields
• Quartic K3 surfaces without nontrivial automorphisms
• Explicit Riemann-Roch spaces in the Hilbert class field
• Fast evaluation of some p-adic transcendental functions
• p-adic integration on bad reduction hyperelliptic curves
• Computation of the divided Frobenius modulo p on the cristalline cohomology of some covering of the porjective line
• Sub-Linear Point Counting for Variable Separated Curves over Prime Power Rings
• Improved Complexity Bounds for Counting Points on Hyperelliptic Curves
• Computing zeta functions of generic projective hypersurfaces in larger characteristic
• Point Counting on Non-Hyperelliptic Genus 3 Curves with Automorphism Group $\mathbb{Z}/2\mathbb{Z}$ using Monsky-Washnitzer Cohomology
• Class number and regulator computation in cubic function fields
• A point counting algorithm using cohomology with compact support