Elliptic curves with a prescribed number of points

Given a prime $p$ and a target $N$ allowed by Hasse's theorem, some elliptic curve over $\mathbb{F}_p$ has exactly $N$ points, but finding one is hard when both $p$ and $N$ are fixed and the associated CM discriminant is large. The task is a practical algorithm for that case, at sizes of $2^{80}$ and beyond.

Problem

Let $p$ be a prime and $N$ an integer with $|N - (p + 1)| < 2\sqrt{p}$. Put $t = p + 1 - N$, so that a curve with $N$ points has Frobenius trace $t$, and consider the discriminant $t^2 - 4p < 0$.

Task. Give an algorithm that, on input $(p, N)$ with $p > 2^{80}$ and the squarefree part of $t^2 - 4p$ large, outputs the coefficients of an elliptic curve $E/\mathbb{F}_p$ with $\#E(\mathbb{F}_p) = N$, within minutes.

Background

The standard tool is the complex multiplication (CM) method. For a discriminant $D$ with $t^2 - v^2 D = 4p$, a root modulo $p$ of the Hilbert class polynomial $H_D$ is the $j$-invariant of a curve with trace $\pm t$, and a quadratic twist fixes the sign [1, 5]. When $p$ may be chosen to suit $N$, one takes $|D|$ small and the method is fast in practice [3, 5]; this underlies elliptic-curve primality proving [1]. When both $p$ and $N$ are prescribed, $D$ is forced by $t^2 - 4p$ and is typically about as large as $p$. Since $H_D$ has degree $h(D) \approx \sqrt{|D|}$ and total size about $|D| \log |D|$ bits, the method is then hopeless.

What is known

• With optimised implementations, Hilbert class polynomials can be computed for $|D|$ up to about $10^{13}$, when they already take several terabytes; other class invariants reach about $10^{15}$ and, with more advanced techniques, $10^{16}$ [2, 5].
• For $p > 2^{80}$ and $|D|$ comparable to $p$, no practical method is known, and Epoch expects that new ideas are needed.
• Fast constructions of this kind would give shorter certificates of primality, in the spirit of Pomerance's very short primality proofs [4], and have uses in cryptography (Epoch's summary).

What would count as progress

• A program that, for such challenges, returns curve coefficients. Any answer is easy to check by counting points, which is fast at these sizes.
• Epoch scores submissions with its own verifier: a Python or Sage program receives $p$ and $N$ on the command line and prints the curve's $a$-invariants. It is run on up to 20 challenges within 30 minutes (the submitter may fix the bit size of $p$, the prime $p$ or the target $N$), and it succeeds if it answers a challenge with $p > 2^{80}$ correctly.
• An algorithm whose running time is, provably or heuristically, subexponential in the bit length of $p$ would be the substantive advance.

References

1. A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Math. Comp. 61 (1993), 29–68. doi:10.1090/S0025-5718-1993-1199989-X
2. A. V. Sutherland, Computing Hilbert class polynomials with the Chinese remainder theorem, Math. Comp. 80 (2011), 501–538. doi:10.1090/S0025-5718-2010-02373-7
3. R. Bröker and P. Stevenhagen, Efficient CM-constructions of elliptic curves over finite fields, Math. Comp. 76 (2007), 2161–2179. doi:10.1090/S0025-5718-07-01980-1
4. C. Pomerance, Very short primality proofs, Math. Comp. 48 (1987), 315–322. doi:10.1090/S0025-5718-1987-0866117-4
5. A. V. Sutherland, Ring class fields and the CM method, MIT 18.783 lecture notes, lecture 21 (2023). math.mit.edu/classes/18.783/2023/LectureNotes21.pdf

Source

Imported from FrontierMath: Open Problems, elliptic-curve-point-count, 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.