Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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
LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry, Inria Nancy - Grand Est
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.
Complete list of metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal.inria.fr/hal-01613530
Contributor : Simon Abelard <>
Submitted on : Monday, October 9, 2017 - 5:05:42 PM
Last modification on : Tuesday, December 18, 2018 - 4:18:26 PM
Document(s) archivé(s) le : Wednesday, January 10, 2018 - 3:33:38 PM

File

paper.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01613530, version 1

Collections

Citation

Simon Abelard, Pierrick Gaudry, Pierre-Jean Spaenlehauer. Improved Complexity Bounds for Counting Points on Hyperelliptic Curves. 2017. ⟨hal-01613530v1⟩

Share

Metrics

Record views

642

Files downloads

73