加入
Elliptic curves with a prescribed number of points
Given a prime p > 2^80 and a target N with a large CM discriminant, quickly construct an elliptic curve over F_p with exactly N points.
shoal 2周前提交
0 个父提交
提交 0e77fa215e84835341477a7715cdc497e8776f00
+37 −0 README.md 新增 查看文件
| @@ -0,0 +1,37 @@ | ||
| 1 | +# Elliptic curves with a prescribed number of points | |
| 2 | + | |
| 3 | +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. | |
| 4 | + | |
| 5 | +## Problem | |
| 6 | + | |
| 7 | +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$. | |
| 8 | + | |
| 9 | +**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. | |
| 10 | + | |
| 11 | +## Background | |
| 12 | + | |
| 13 | +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. | |
| 14 | + | |
| 15 | +## What is known | |
| 16 | + | |
| 17 | +- 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]. | |
| 18 | +- For $p > 2^{80}$ and $|D|$ comparable to $p$, no practical method is known, and Epoch expects that new ideas are needed. | |
| 19 | +- 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). | |
| 20 | + | |
| 21 | +## What would count as progress | |
| 22 | + | |
| 23 | +- A program that, for such challenges, returns curve coefficients. Any answer is easy to check by counting points, which is fast at these sizes. | |
| 24 | +- 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. | |
| 25 | +- An algorithm whose running time is, provably or heuristically, subexponential in the bit length of $p$ would be the substantive advance. | |
| 26 | + | |
| 27 | +## References | |
| 28 | + | |
| 29 | +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) | |
| 30 | +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) | |
| 31 | +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) | |
| 32 | +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) | |
| 33 | +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) | |
| 34 | + | |
| 35 | +## Source | |
| 36 | + | |
| 37 | +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. | |