Polynomial Time Zeta Functions for Hyperelliptic Curves

Definitions and mathematical statement

Let $p$ be a prime, let $r\geq 1$, and put $q=p^r$. For a smooth projective geometrically connected hyperelliptic curve $C/{\mathbb{F}}_q$ of genus $g$, define \[ N_n(C)=\#C({\mathbb{F}}_{q^n}),\qquad Z(C/{\mathbb{F}}_q,T)=\exp\!\left(\sum_{n\geq 1}N_n(C)\frac{T^n}{n}\right). \] The zeta function has the form \[ Z(C/{\mathbb{F}}_q,T)=\frac{P_C(T)}{(1-T)(1-qT)},\qquad P_C(T)\in{\mathbb{Z}}[T],\quad \deg P_C=2g. \] Thus exact computation can be expressed as determining the coefficients of $P_C(T)$. This uses the usual smooth projective curve convention; the supplied statement does not specify an input model or output encoding.

Source question. Can the zeta function, denoted $Z_p(T)$ in the source, of a genus-$g$ hyperelliptic curve over a finite field of characteristic $p$ be computed in time polynomial simultaneously in $g$ and $\log p$? A uniform polynomial bound would mean a bound of the form \[ A\left(1+g+\log_2 p\right)^c, \] with constants $A,c>0$ independent of the curve, $g$, and $p$, once the input representation and computational model have been fixed.

Unresolved scope. The source specifies characteristic $p$, not that the field equals ${\mathbb{F}}_p$. It does not state whether $r$ is one, fixed, bounded, or an additional complexity parameter. Consequently, the displayed bound cannot be assigned an unqualified quantifier over arbitrary extension fields from the supplied evidence. If the intended field is ${\mathbb{F}}_p$, the question specializes to a uniform algorithm for all such curves over all prime fields. If general ${\mathbb{F}}_{p^r}$ is intended, the permitted dependence on $r$ must be supplied. The source also leaves deterministic versus randomized computation, the runtime guarantee, and the encoding of curves and finite fields unspecified. No restriction excluding characteristic two is supplied.

Short English statement

The question asks for an exact algorithm computing the zeta function of a hyperelliptic curve in time polynomial jointly in its genus and the logarithm of the field characteristic. The role of the finite-field extension degree and the computational model remain unspecified. The supplied registry labels the problem open; this is a supplied status, not an independently verified conclusion.

Sources

• Supplied local registry record: data/unsolvedmath/problems.json, permanent UnsolvedMath ID $30002918$, source problem code catalogue entry, title "Polynomial Time Zeta Functions for Hyperelliptic Curves." The record gives proposed year 2015 and names no proposer.
• Supplied report citation: Explicit Methods in Number Theory (2016), Oberwolfach Reports, pp. 1809--1866, DOI 10.4171/owr/2015/32. Original Oberwolfach report: https://doi.org/10.4171/owr/2015/32. The supplied background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature source, labeled "Harvey primary paper": https://doi.org/10.4007/annals.2014.179.2.7.
• Supplied literature source, labeled "Sutherland primary paper": https://arxiv.org/abs/2004.10189.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the problem open and reports important average-case polynomial bounds while describing polynomial time simultaneously in genus and $\log p$ for the stated computation as a major open question. This is supplied dated curation derived from the OWR record, not independently verified literature assessment. The record expressly requests independent verification of time-sensitive status and cited claims.