Improved Complexity Bounds for Counting Points on Hyperelliptic Curves

Simon Abelard 1 Pierrick Gaudry 1 Pierre-Jean Spaenlehauer 1
1 CARAMBA - Cryptology, arithmetic : algebraic methods for better algorithms
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [29 references]  Display  Hide  Download
https://hal.inria.fr/hal-01613530
Contributor : Pierre-Jean Spaenlehauer <>
Submitted on : Thursday, June 7, 2018 - 9:55:49 AM
Last modification on : Thursday, June 6, 2019 - 7:44:25 AM
Long-term archiving on : Saturday, September 8, 2018 - 12:33:22 PM

File

paper.pdf
Files produced by the author(s)

Identifiers

Collections

INSMI | UNIV-LORRAINE | LORIA | LORIA-ALGO | INRIA

Citation

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

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

480

Files downloads

450

Contact


archive-ouverte@inria.fr