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.
https://hal.inria.fr/hal-01613530
Contributeur : Pierre-Jean Spaenlehauer
<>
Soumis le : jeudi 7 juin 2018 - 09:55:49
Dernière modification le : jeudi 7 février 2019 - 15:13:20
Document(s) archivé(s) le : samedi 8 septembre 2018 - 12:33:22
Simon Abelard, Pierrick Gaudry, Pierre-Jean Spaenlehauer. Improved Complexity Bounds for Counting Points on Hyperelliptic Curves. Foundations of Computational Mathematics, Springer Verlag, In press, 〈10.1007/s10208-018-9392-1〉. 〈hal-01613530v2〉
