Improved Complexity Bounds for Counting Points on Hyperelliptic Curves

Simon Abelard, Pierrick Gaudry, Pierre-Jean Spaenlehauer

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 approache…