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.
Type de document :
Pré-publication, Document de travail
To appear in Foundations of Computational Mathematics. 2018
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01613530
Contributeur : Pierre-Jean Spaenlehauer <>
Soumis le : jeudi 7 juin 2018 - 09:55:49
Dernière modification le : vendredi 8 juin 2018 - 01:17:20

Fichier

paper.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01613530, version 2

Collections

Citation

Simon Abelard, Pierrick Gaudry, Pierre-Jean Spaenlehauer. Improved Complexity Bounds for Counting Points on Hyperelliptic Curves. To appear in Foundations of Computational Mathematics. 2018. 〈hal-01613530v2〉

Partager

Métriques

Consultations de la notice

140

Téléchargements de fichiers

36