A 256-bit elliptic-curve discrete logarithm

Elliptic-curve cryptography is secure only if, given points $P$ and $Q = xP$ on a curve over a large prime field, recovering the integer $x$ is infeasible. Epoch has published one such instance at full cryptographic size. Solving it in reasonable time would point to a new attack on the elliptic-curve discrete logarithm problem (ECDLP), or to a hidden weakness in this particular curve.

Problem

Let $p$ be the 256-bit prime below and $E\colon y^2 = x^3 + ax + b$ the curve over $\mathbb{F}_p$ with the given $a, b$ . The point $P \in E(\mathbb{F}_p)$ has prime order $n$ , a 254-bit prime, and $\#E(\mathbb{F}_p) = 5n$ . The point $Q$ equals $xP$ for a secret integer $1 \le x < n$ , where $xP$ is $P$ added to itself $x$ times.

p  = 92031864238688105485400538143121826382268912998421731683072033206257804487869
a  = 66780434313013275323552928748270304481793221171615836760742707201070562072251
b  = 49926646401131159709065076432340744650532242327390476058390067276099410301761
Px = 38644201185363417798191368696978811687737990190927559170532558153854800741642
Py = 44805905068903897561820523795034068749084951450263356538447620424400005028012
Qx = 54096648540016620506320945354369315155659910460053503439381018376158456438152
Qy = 23176800742290374932252879903926227937053123957837615098744936554616726258932
n  = 18406372847737621097080107628624365276513063062857122317960690589425712086189

Task. Find $x$ .

Background

Koblitz and Miller independently proposed basing public-key cryptography on elliptic curves in the mid-1980s [1, 2]. Its security rests on the presumed hardness of this problem for well-chosen curves over prime fields. A generic square-root method such as Pollard's rho [3] would need on the order of $\sqrt{n} \approx 2^{127}$ group operations here, far beyond any computer. Research continues on algebraic attacks, for example index calculus with summation polynomials, surveyed by Galbraith and Gaudry [4].

What is known

The numbers above are consistent: $p$ and $n$ are prime, $P$ and $Q$ lie on $E$ , $nP = nQ = O$ , and $5n$ lies in the Hasse interval around $p + 1$ (our check).
Epoch chose the instance to be hard and names two risks: that a brute-force search might succeed in the allowed time, or that the curve has unexpected structure making it easier than intended.
No solution has been reported.

What would count as progress

The integer $x$ . Verification is one scalar multiplication: check that $xP = Q$ .
Epoch scores submissions with its own verifier, which accepts the decimal value of $x$ .
What matters most is the method: an attack that works for this curve and explains why, or a demonstration that the instance has an exploitable weakness.

References

N. Koblitz, Elliptic curve cryptosystems, Math. Comp. 48 (1987), 203–209. doi:10.1090/S0025-5718-1987-0866109-5
V. S. Miller, Use of elliptic curves in cryptography, CRYPTO '85, Lecture Notes in Comput. Sci. 218 (1986), 417–426. doi:10.1007/3-540-39799-X_31
J. M. Pollard, Monte Carlo methods for index computation (mod $p$ ), Math. Comp. 32 (1978), 918–924. doi:10.1090/S0025-5718-1978-0491431-9
S. D. Galbraith and P. Gaudry, Recent progress on the elliptic curve discrete logarithm problem, Des. Codes Cryptogr. 78 (2016), 51–72. doi:10.1007/s10623-015-0146-7 (ePrint 2015/1022)

Source

Imported from FrontierMath: Open Problems, elliptic-curve-discrete-logarithm, curated by Epoch AI. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.