Semaev's Auxiliary Elliptic-Curve Index-Calculus Algorithm

Research-attempt provenance

Definitions and mathematical statement

Shared notation.

Standard number systems are $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$. Specialized notation and index ranges follow the cited source and the definitions below.

For a fixed elliptic curve, a summation polynomial vanishes on abscissas of points whose sum in the curve group is zero. $\mathbb F_p$ is the field of residues modulo the prime $p$.

Record scope and qualifications.

The catalogue title is retained as metadata. Named certificates, contracts, bounds or frameworks in that title are not asserted as results of the original source extract. The elliptic curve, number $n$, permitted $\delta$, and meaning of required by the construction are not specified in the supplied question; no universal running-time bound is inserted.

Source-record limitation: The curve, n/delta regime, and requirement from the omitted index-calculus construction are absent; the quantified algorithm target is not recoverable.

Statement recorded in the supplied source.

Let $f_{n+1}$ be Semaev's $(n+1)$-st summation polynomial. Given a prime $p$ and $x\in\mathbb{F}_p$, is there an effective general algorithm that finds integers $x_1,\ldots,x_n$, each of size at most $p^{1/n+\delta}$, such that $f_{n+1}(x_1,\ldots,x_n,x)\equiv0\pmod p$ whenever such a tuple is required by the index-calculus construction? [S2]

Source status.

The supplied catalogue labels this source record open; that metadata was checked against the supplied snapshot on 2026-10-11. The label is preserved for provenance and is not an independent verification of present open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

Find small coordinates satisfying the elliptic-curve relation needed by the cited index-calculus method.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30000158 (OWR-768-008). Catalogue curation and metadata: CC BY 4.0. The source extract is retained; definitions, English summaries and qualifications are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Finite Fields: Theory and Applications $2005$, Oberwolfach Reports, DOI 10.4171/owr/2004/54, pp. 2913--2970 https://doi.org/10.4171/owr/2004/54.
• Source-specific Oberwolfach Reports licences, including CC BY-SA 4.0 where applicable, are retained; see THIRD_PARTY_NOTICES.md.

Preparation and review.

The original source and UnsolvedMath contributors retain attribution for the source extract. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, scope notes and formatting. No new human mathematical authorship or independently verified solution is asserted. Permanent source ID 30000158 and code OWR-768-008 checked against the complete supplied registry and current repository. Distinct upstream records, including repeated questions and broad or damaged extracts, are retained for complete coverage of the source CS category. A repeated record is not a new independent conjecture. Complete mathematical-equivalence and current-literature review has not been performed. Preparation and final review follow contribution prompts C and D, with source gaps disclosed. Structural and rendering checks do not establish a new theorem or open status.

Literature and context check

Semaev's primary report contribution, pp. 2959--2960, was read. It fixes a curve $Y^2=X^3+AX+B$, defines summation-polynomial zeros using points over the algebraic closure, and discusses the cost of finding small-coordinate solutions for a random residue. Its usefulness depends on that cost, not on mere finite computability. The following two-variable algorithm is a restricted exact search calculation; no missing general parameter regime is reconstructed.

Research attempt: Finite search versus a useful relation algorithm

Once a finite polynomial $f_{n+1}$ and a nonnegative integer bound $H\geq0$ are supplied, exhaustive enumeration of integers $|x_i|\leq H$ terminates and either finds a zero or certifies none. There are $(2H+1)^n$ tuples before reducing repeated residues. For $H$ of order $p^{1/n+\delta}$, this is of order $p^{1+n\delta}$ for fixed $n,\delta$. Such a finite algorithm is not automatically the fast auxiliary routine the source needs, and is exponential in $\log p$.

For a more concrete improvement, take $n=2$, a prime $p>3$ with $p\equiv3\pmod4$, and the nonsingular curve coefficients $A,B\in\mathbb F_p$. For the supplied target abscissa $x$, the source's explicit third summation polynomial, using its symmetry to order the variables as $(u,x,v)$, is \[ f_3(u,x,v)=a_u v^2+b_u v+c_u, \] where \[ a_u=(u-x)^2,\quad b_u=-2((u+x)(ux+A)+2B),\quad c_u=(ux-A)^2-4B(u+x). \] Enumerate all distinct residues having an integer representative of absolute value at most $H$. For each $u$, solve this quadratic in $v$ and retain a root only if its balanced integer representative has absolute value at most $H$. If $a_u=0$, solve the linear equation when $b_u\ne0$; when $a_u=b_u=0$, there is no root if $c_u\ne0$, and every $v$ is a root if $c_u=0$, in which case $v=0$ is admissible. These cases prevent division by zero.

When $a_u\ne0$, compute $\Delta=b_u^2-4a_uc_u$. For $\Delta=0$ there is one root $-b_u/(2a_u)$. For $\Delta\ne0$, test $\Delta^{(p-1)/2}=1$. This is equivalent to being a square: the $(p-1)/2$ distinct nonzero squares all satisfy that equation, and a polynomial of degree $(p-1)/2$ has at most that many roots. Here $z^{p-1}=1$ for nonzero $z$ follows by comparing the product of all nonzero field elements with the same product multiplied by $z$. If the test succeeds, $w=\Delta^{(p+1)/4}$ obeys $w^2=\Delta$, and the roots are $(-b_u\pm w)/(2a_u)$. If it fails there are no roots. These statements follow directly by completing the square and cover all quadratic roots.

Repeated squaring and Fermat inversion use $O(\log p)$ field multiplications per candidate. Thus the search uses \[ O(\min\{p,2H+1\}\log p) \] field operations, with polynomial-in-$\log p$ bit cost per operation under ordinary integer arithmetic. Balanced representatives are sufficient because every residue's least absolute representative is the one closest to zero, and the allowed interval is symmetric. The algorithm finds a bounded pair if and only if one exists for this $f_3$ problem.

This does not provide the desired higher-order index-calculus improvement. With $H\approx p^{1/2+\delta}$, even this restricted routine has about that many candidate abscissas, and substituting into the report's $n=2$ cost expression does not beat its square-root comparison baseline. Also a summation-polynomial zero need not certify that each point lies over $\mathbb F_p$: the source defines the geometric relation over the algebraic closure. Already $f_2(u,u)=0$ even if $u^3+Au+B$ is a nonsquare, in which case there is no rational point with that abscissa. Rational-point restrictions in a factor base require a separate check.

Verification and adversarial audit

The quadratic degeneracies, zero discriminant, nonsquare discriminant, and balanced-residue bound are all included. The square-root formula is confined to $p\equiv3\pmod4$. The algorithm solves the displayed polynomial equation exactly; it does not guarantee a solution exists or silently change algebraic-closure points into rational points.

Audit corrections.

Effective finite enumeration was separated from the cost threshold needed by the source. The explicit $f_3$ formula and its degenerate cases were used without assuming an unspecified general solver.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

No sufficiently fast general-$n$ small-solution algorithm, success-distribution analysis, or complete index-calculus attack is obtained. The finite decision search and exact restricted quadratic solver are auxiliary known-style computations, leaving the original missing efficiency regime unresolved.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The calculations below the preserved source statement investigate a concrete route, but establish no substantiated new progress toward the entire original target. Known special cases and failed sufficient conditions are not credited as a solution.

References

The original source references and catalogue attribution are preserved in the Sources section above. The following URLs were actually consulted for this attempt; retention of an additional original reference does not claim fresh consultation of it.

• https://ems.press/content/serial-article-files/45972 (consulted 2026-10-11).

Model and contributor disclosure

OpenAI gpt-6-astra, requested reasoning configuration ultra, generated this research attempt on 2026-10-11. The exact serving revision is not exposed. Codex GPT-6 performed orchestration, repository-format review, and written mathematical review at the declared scope; its exact serving revision is also not exposed. The mathematical route, boundary checks and final adversarial self-audit followed contribution prompts A then B in docs/contribution_prompts.md, after reading CONTRIBUTING.md. Python 3.14.2 assembled the standalone documents; any mathematical computation is specified in Verification. No theorem prover was used. No human mathematical authorship, substantial human proof correction, or independent human proof checking is asserted. Model-assisted review, source retrieval, and structural checks do not establish correctness or novelty. Full private reasoning transcripts are unavailable as reproducibility artifacts; the complete arguments, inputs and outcomes actually used are stated here or in the companion batch audit.

Final status

Unresolved as a new research contribution. This is a concrete route investigation, not a claim of new complete resolution or a current-status certification. A known answer reproduced for context does not become a new contribution. The catalogue's source-status label is preserved; this attempt status does not assert that a source-labelled solved question is open.