Deterministically generating Picard groups of hyperelliptic curves over finite fields

Abstract

Let $\epsilon >0$. In this article we will present a deterministic algorithm which does the following. The input is a hyperelliptic curve $C$ of genus $g$ over a finite field $k$ of cardinality $q$ given by $y^2+h(x)y=f(x)$ such that the $x$-coordinate map is ramified at $\infty$. In time $O(g^{2+\epsilon }{q}^{1/2+\epsilon })$ the algorithm outputs a set of generators of the Picard group ${\mathrm{Pic}}_k^0(C)$. This extends results which others have obtained when $g=1$. In this article we introduce a combinatorial tool, the `shape parameter', which we use together with character sum estimates from class field theory to deduce the statement.

arXiv comment15 pages