Improved Complexity Bounds for Counting Points on Hyperelliptic Curves

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 modelling 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)^{c g})$$ as q grows and the characteristic is large enough.