OpenFrontiers
Join
← Back to the index
OP-11954OpenCryptography

The Elliptic-Curve Discrete Logarithm Problem (ECDLP)

The Elliptic-Curve Discrete Logarithm Problem (ECDLP). Major advance problem from Epoch AI’s FrontierMath: Open Problems; answers are checked by a verifier program.

MSC 94A60 · CryptographyMSC 11Y16 · Number-theoretic algorithms; complexityMSC 14G50 · Applications to coding theory and cryptography of arithmetic geometry

Epoch field label “Number theory” mapped to MSC2020 94A60 for The Elliptic-Curve Discrete Logarithm Problem (ECDLP). https://epoch.ai/frontiermath/open-problems/elliptic-curve-discrete-logarithm Not an author-supplied code.

Licensed source statementAs of Epoch AI data archive updated 2026-10-07; status as labeled by EpochSource & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

This problem tests whether an AI model can attack elliptic-curve discrete logarithms. The assumption that attacking elliptic-curve discrete logarithms is hard forms a foundation of elliptic curve cryptography, and the ECDLP is well-known; see here for a survey.

The ECDLP asks for the following. Let pp be a large prime number, and let

E/Fp:y2=x3+ax+bE/\mathbb F_p:\quad y^2=x^3+ax+b

be an elliptic curve. Let P∈E(Fp)P\in E(\mathbb F_p) be a point of large prime order rr, and let

Q=nPQ=nP

for some integer nn.

The problem is to compute the discrete logarithm

n=log⁡P(Q)(modr).n=\log_P(Q)\pmod r.

In other words, given only the elliptic curve, PP, and QQ, recover nn.

For this benchmark, the instance of the problem is chosen to be hard, but not quite as hard as instances used in real cryptographic protocols. If AI can solve this problem in an hour, it would suggest that the AI found a new attack or exploited some structure of the elliptic curve.

The verifier checks that the solution is correct by computing nPnP and checking that Q=nPQ = nP. The main risks are that the models manage to brute-force a solution in the allowed time, or that the problem instance, which is chosen to be difficult, had some unexpected structure that made it less difficult than intended.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

FrontierMath: Open Problems lists this problem with notability “Major advance”, field “Number theory” and type “Algorithm”. Each problem has a bespoke verifier program, so a proposed answer can be checked automatically.

Verifiable task — Epoch prompt, verbatim

Let p be a prime. You are given a curve

    E/F_p : y^2 = x^3 + a*x + b,

a point P in E(F_p) of prime order n, and a point

    Q = xP,

where xP denotes elliptic-curve scalar multiplication: the point obtained by adding P to
itself x times under the group law on E. (The scalar x here is an integer, distinct from the
affine coordinate variable x in the curve equation above.)

The Elliptic Curve Discrete Logarithm Problem is to recover x from the data (p, a, b, P, Q).

The public challenge is p, a, b, P, Q, n, h, where #E(F_p) = h*n and h is small:

    p = 92031864238688105485400538143121826382268912998421731683072033206257804487869
    a = 66780434313013275323552928748270304481793221171615836760742707201070562072251
    b = 49926646401131159709065076432340744650532242327390476058390067276099410301761
    P = (38644201185363417798191368696978811687737990190927559170532558153854800741642, 44805905068903897561820523795034068749084951450263356538447620424400005028012)
    Q = (54096648540016620506320945354369315155659910460053503439381018376158456438152, 23176800742290374932252879903926227937053123957837615098744936554616726258932)
    n = 18406372847737621097080107628624365276513063062857122317960690589425712086189
    h = 5

## Task

Recover x (the private answer): the integer x with 1 <= x < n such that Q = xP.

## Submission

Submit x by calling the `submit_answer` tool with `secret_x` set to the decimal integer,
written as a string (for example "123456789").

Progress & source assessment

Epoch lists this problem as unsolved in its data archive updated 7 October 2026. Earlier AI attempts are not displayed by Epoch.

References
  1. [1]Epoch AI, ‘FrontierMath: Open Problems’. Published online at epoch.ai. Retrieved from https://epoch.ai/frontiermath/open-problems (data updated 7 October 2026). — The Elliptic-Curve Discrete Logarithm Problem (ECDLP) linkCC BY 4.0 (Epoch AI data and problem pages); attributed reproduction of problem descriptions and verbatim task prompts.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.