Improved Complexity Bounds for Counting Points on Hyperelliptic Curves

2017/10/10 by Simon Abelard, Abelard, Simon, Pierrick Gaudry +3 · 1 citation
Computer Science · Mathematics · #Algebraic Geometry (math.AG) #Algebraic Geometry and Number Theory #Cryptography and Residue Arithmetic #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #Polynomial and algebraic computation #Symbolic Computation (cs.SC)

paper · doi:10.48550/arxiv.1710.03448

openalex publication_date 2017/10/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a probabilistic Las Vegas algorithm for computing the local zeta function of a hyperelliptic curve of genus g defined over \mathbbF_q. It is based on the approaches by Schoof and Pila combined with a modeling of the ℓ-torsion by structured polynomial systems. Our main result improves on previously known complexity bounds by showing that there exists a constant c>0 such that, for any fixed g, this algorithm has expected time and space complexity O((log q)^cg) as q grows and the characteristic is large enough.

Cited by

• Lifting L-polynomials of genus 2 curves

Related

• Counting points on hyperelliptic curves with explicit real\n multiplication in arbitrary genus
• Point counting in families of hyperelliptic curves in characteristic 2
• Counting points on hyperelliptic curves in average polynomial time
• Complexity of counting points on curves and the factor P₁(T) of the zeta function of surfaces
• Point counting in families of hyperelliptic curves