O24 — Finding a point on an elliptic curve

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Integers are supplied in binary; polynomial time means a polynomial number of classical bit operations in total input length. Given a prime $p$ and positive integer representatives $a,b$ with $4a^3+27b^2\not\equiv0\pmod p$, an affine point is a pair $x,y\in\mathbb Z/p\mathbb Z$ satisfying $y^2=x^3+ax+b$.

Statement recorded in the supplied source.

Is there a deterministic polynomial-time algorithm which outputs an affine point on every promised curve? [S2]

Short English statement

Can one deterministically find finite coordinates of a point on the given nonsingular elliptic curve in polynomial time?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 8400028 (AMR-083-0028). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Leonard M. Adleman and Kevin S. McCurley, Open Problems in Number Theory Complexity, II, in Algorithmic Number Theory, LNCS 877 (1994), pp. 291--322, C24/O24, manuscript p. 17 (LNCS p. 307). https://mccurley.org/papers/open.ps.gz.