Efficient Relation Generation for Curve Class Groups

Definitions and mathematical statement

Let $T_{\mathrm{rel}}$ denote the heuristic expected running time of the relation-generation stage of the discrete-logarithm algorithm referred to in the supplied record. The record gives the target bound \[ T_{\mathrm{rel}}=\exp\!\left(O\!\left(\max\{\log q,\,n(\log q)^{1/2}\}\right)\right) \] and the hypothesis \[ n\leq C\log q. \] The supplied open question is whether this heuristic expected running-time bound can be achieved for broader families of elliptic curves, or for curves of any fixed genus, by weakening or removing that hypothesis. Here fixed genus means that the genus is held constant as the input parameters vary; the record does not specify whether the implied constant in $O(\cdot)$ may depend on the genus.

Unresolved formulation qualifications. The supplied record does not define $q$, $n$, or $C$, identify the underlying fields or original family of curves, specify the discrete-logarithm algorithm or its relations, or state the heuristic assumptions and probability model underlying the expectation. Consequently, it does not determine a fully quantified computational problem or a precise enlargement of the admissible input family. The displayed expression and hypothesis are retained without assigning unsupported meanings to their parameters.

The supplied literature assessment additionally discusses an efficient algorithm that outputs a generating system for a degree-zero class group with certainty, particularly in fixed genus greater than one. It says that randomized potential generating systems do not establish that guarantee. The record does not explain how this certainty requirement relates to the heuristic relation-generation question above; it therefore remains a separate, unresolved qualification.

Short English statement

The question asks whether the stated heuristic expected time for generating discrete-logarithm relations extends to broader elliptic-curve families or to curves of any fixed genus when $n\leq C\log q$ is relaxed or removed. Missing parameter definitions and algorithmic hypotheses prevent a fully precise formulation. The supplied discussion of certain class-group generation requires clarification.

Sources

• Local UnsolvedMath registry: supplied complete record for permanent ID $30002381$, title "Efficient Relation Generation for Curve Class Groups," exact source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. The record gives proposed year 2013 and names no proposer.
• Supplied source citation: Explicit Methods in Number Theory (2014), Oberwolfach Reports, pp. 2035--2082, DOI 10.4171/owr/2013/35. Supplied source URL and literature reference "Oberwolfach Report 35/2013": https://doi.org/10.4171/owr/2013/35. The background describes these reports as records of mathematical workshops and their open-problem discussions.
• Supplied literature assessment, checked 2026-08-21: the record labels the problem open and states that, for fixed genus greater than one, the required efficient algorithm producing a degree-zero class-group generating system with certainty is still not established, and that randomized potential generating systems do not resolve this guarantee. This is supplied dated curation, not an independently verified literature assessment. The background expressly requests independent verification of time-sensitive status and cited claims.
• Supplied statement status: corrected_verified. The record reports that its clean statement was checked against the official Oberwolfach report and preserves the hypotheses, notation, and open target. This verification claim is part of the supplied metadata; no independent source consultation or mathematical verification is asserted here.