Improved Complexity Bounds for Counting Points on Hyperelliptic Curves - Archive ouverte HAL Access content directly
Journal Articles Foundations of Computational Mathematics Year : 2019

## Improved Complexity Bounds for Counting Points on Hyperelliptic Curves

Simon Abelard
• Function : Author
• PersonId : 1020341
Pierrick Gaudry
Pierre-Jean Spaenlehauer

#### Abstract

We present a probabilistic Las Vegas algorithm for computing the local zeta function of a hyperelliptic curve of genus $g$ defined over $\mathbb{F}_q$. It is based on the approaches by Schoof and Pila combined with a modeling of the $\ell$-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.

### Dates and versions

hal-01613530 , version 1 (09-10-2017)
hal-01613530 , version 2 (07-06-2018)

### Identifiers

• HAL Id : hal-01613530 , version 2
• ARXIV :
• DOI :

### Cite

Simon Abelard, Pierrick Gaudry, Pierre-Jean Spaenlehauer. Improved Complexity Bounds for Counting Points on Hyperelliptic Curves. Foundations of Computational Mathematics, 2019, 19 (3), pp.591-621. ⟨10.1007/s10208-018-9392-1⟩. ⟨hal-01613530v2⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

715 View