Improved complexity bounds for counting points on hyperelliptic curves

DOI10.1007/s10208-018-9392-1zbMath1470.11170arXiv1710.03448OpenAlexW2763453947WikidataQ129643498 ScholiaQ129643498MaRDI QIDQ2420634

Pierrick Gaudry, Pierre-Jean Spaenlehauer, Simon Abelard

Publication date: 6 June 2019

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1710.03448

zbMATH Keywords

hyperelliptic curveslocal zeta functiongeometric resolutionmulti-homogeneous polynomial systemsSchoof-Pila's algorithm

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Curves over finite and local fields (11G20) Zeta and (L)-functions in characteristic (p) (11M38)

Related Items (6)

Counting points on genus-3 hyperelliptic curves with explicit real multiplication ⋮ Unnamed Item ⋮ Counting points on hyperelliptic curves of type \(y^2=x^{2g+1}+ax^{g+1}+bx\) ⋮ Hensel-lifting torsion points on Jacobians and Galois representations ⋮ Counting points on hyperelliptic curves with explicit real multiplication in arbitrary genus ⋮ Curves, Jacobians, and cryptography

Uses Software

• Kronecker

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Genus 2 point counting over prime fields
• Definability and fast quantifier elimination in algebraically closed fields
• Counting points on curves over finite fields
• Counting points on curves using a map to \(\mathbf P^1\). II.
• Counting points on curves using a map to $\mathbf {P}^1$
• Modern Computer Algebra
• Mathematics of Public Key Cryptography
• Counting Points on Genus 2 Curves with Real Multiplication
• A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets
• Fast computation of a rational point of a variety over a finite field
• Computing zeta functions of arithmetic schemes
• Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p
• Computing in the Jacobian of a Hyperelliptic Curve
• Bertini and his two fundamental theorems
• On the analogue of the division polynomials for hyperelliptic curves.
• Finding Suitable Curves for the Elliptic Curve Method of Factorization
• Deformation theory and the computation of zeta functions
• Frobenius Maps of Abelian Varieties and Finding Roots of Unity in Finite Fields
• The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
• Handbook of Elliptic and Hyperelliptic Curve Cryptography
• A Gröbner free alternative for polynomial system solving
• Counting points on curves and Abelian varieties over finite fields

This page was built for publication: Improved complexity bounds for counting points on hyperelliptic curves