O27 — Elliptic curves of prescribed order

Definitions and mathematical statement

For a prime $p>3$, an elliptic curve over $\mathbb F_p$ may be represented by \[ E_{A,B}:y^2=x^3+Ax+B,\qquad 4A^3+27B^2\ne0\text{ in }\mathbb F_p. \] Its rational points consist of the affine solutions $(x,y)\in\mathbb F_p^2$ together with one point at infinity. Write $\#E_{A,B}(\mathbb F_p)$ for this total, including that point.

Given $p$ and a positive integer $n$ in binary, with the promise that some elliptic curve over $\mathbb F_p$ has exactly $n$ rational points, can a deterministic classical algorithm construct one in time polynomial in $\log p+\log n$? In characteristic greater than three, the required output is a pair $(A,B)$ satisfying the displayed nonsingularity condition and $\#E_{A,B}(\mathbb F_p)=n$.

For the two exceptional characteristics, use a nonsingular general Weierstrass equation; their finitely many possibilities can be handled separately. Thus omitting these characteristics from the displayed model does not change the computational question.

The input does not contain a curve with the requested order, an imaginary quadratic class polynomial, or any auxiliary factorization. All construction work counts towards the bound. This is an inverse problem: efficiently counting the points of an already supplied curve is a different task. On inputs where no such curve exists, no behavior is prescribed by this promised-existence formulation.

Short English statement

Can an elliptic curve with any realizable prescribed number of points over a prime field be constructed deterministically in polynomial time?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 8400031 (AMR-083-0031), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Adleman & McCurley - Open Problems in Number Theory Complexity II (1994), O27, p19 / LNCS p309. Original source indexed by AMR-083-0031. https://mccurley.org/papers/open.ps.gz.