# 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](https://doi.org/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](https://doi.org/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](https://doi.org/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](https://doi.org/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](https://math.mit.edu/classes/18.783/2023/LectureNotes21.pdf)

## Source

Imported from [FrontierMath: Open Problems, elliptic-curve-point-count](https://epoch.ai/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.