Generate n⁴-smooth one-shot ECPP certificates by the CM method ("fast ECPP"). Given a prime p, it produces a certificate (p, A, x₀, m, q₁…q_k) that proves p prime and is verifiable in quasi-quadratic time by voneshot.py.

This repository was created in response to the one-shot primality proofs challenge, which defines one-shot ECPP certificates and hosts the verifier. The code was written by Claude Opus 4.8 and Claude Fable 5 in collaboration with Andrew V. Sutherland, using his classpoly library, which implements the algorithms in arXiv:0903.2785 and arXiv:1001.3394.

git clone https://github.com/AndrewVSutherland2/OneShotFastECPP.git && cd OneShotFastECPP
make -j                           # ff_poly -> classpoly -> zp_poly -> ecpp tools (~1 min)
. ./setenv.sh                     # point classpoly at the bundled modular polynomials
./ecpp/oneshotECPP p=$(python3 -c 'print(2**255-19)')

Output is a single line p A x₀ m q₁ … q_k:

57896044618658097711785492504343953926634992332820282019728792003956564819949 \
34272590291611932410078115265478194150993293036704524951758556452491882420894 \
39019257195751330428207690201832939607319582892511312056714375592481312290863 \
260621764559582591965379563027288448623 342527 864107 1396061 15802043 177075901

(Certificates are not unique — your run may print a different valid one.) Verify it with the challenge repo's verifier:

python3 voneshot.py 57896044618658097711785492504343953926634992332820282019728792003956564819949 34272590...
# True

oneshotECPP accepts p=<decimal> or pbits=<n> [seed=<s>] (a random n-bit prime), plus threads=<t>, c=<work ratio>, B0=/B= (initial/max discriminant-scan bounds), and pcache=<file>. The smoothness bound climbs a power-of-2 ladder starting just above n² — prime-product segments are built on demand (and cached in work/pcache/, shared across all prime sizes), the candidate pool widens geometrically in between, and the run stops at the first rung that yields a certificate. Certificates rarely need primes anywhere near n⁴, so even a fully cold run takes seconds at 256 bits.

For a fixed prime p it runs the CM method end to end:

1. Discriminant search — find a CM discriminant D<0 with 4p = t² + |D|v² solvable (Cornacchia over a factor base).
2. Smoothness — keep curve orders N = p+1∓t with N ≡ 0 mod 4 whose n⁴-smooth part exceeds L = (p^{1/4}+1)² (n = ⌈log₂ p⌉); this gives a smooth m | N. Batched with a remainder tree.
3. Class polynomial + root — compute H_D mod p in the best class invariant (via classpoly), find a root over F_p, and convert it to a j-invariant.
4. Curve + point — build the Montgomery curve E_A/F_p with that j and order N, find a point of order m, and emit (p, A, x₀, m, q_i).

See design.md for the full technical writeup and performance.

ecpp/shortECPP.py is a prover for short ECPP certificates in the ShortPrimalityProofs format: a descending chain of levels p = p₀ > p₁ > … with p_{i+1} < √p_i, each level exhibiting a Montgomery curve point of exact order o = m·q where m is n²-smooth and q = p_{i+1} — giving O(n)-bit certificates verifiable in quasi-quadratic time. Unlike a one-shot certificate the discarded cofactor is never factored, so each level only needs its curve order to be "√-semismooth": one prime just below √p, everything else ECM-findable.

Per level it runs this repository's toolchain end to end: dscan (Cornacchia discriminant scan; the maxfb= option bounds the factor base so 10⁵-candidate pools stay affordable at 1000+ bits), smoothtest (batched Bernstein remainder trees against a cached primorial), staged gmp-ecm peeling under a Bayesian index scheduler (coverage ~ln s, per-curve failure discounts, round-robin sub-sweeps, an economic widen-vs-deepen trigger), then classpoly/ cm_method for the winner's curve (2-volcano floor descent when p ≡ 3 mod 4 requires it) and short.gp for the levels below 135 bits. Every chain is verified by vsmallECPP.py plus an independent PARI ellmul cross-check before it is written.

. ./setenv.sh
python3 ecpp/shortECPP.py c=150 threads=32          # nextprime(10^150)
python3 ecpp/shortECPP.py p=<decimal> tag=myprime   # any (probable) prime
# knobs: B0=/Bmax= (discriminant-scan schedule), maxfb= (factor-base cap),
#        resume=1 (replay the winner journal after a crash/preemption), out=<file>

Needs a gmp-ecm binary (CHAIN_ECM env or ecm on PATH). With it, this prover produced the ShortPrimalityProofs table entries for nextprime(10^c), c = 210, …, 310 — the largest a 1030-bit prime exceeding Bernstein's 1025-bit AKS example — in one day on spot instances (≈3,500 CPU core-hours; see reports/short-ecpp-records/ for the full campaign report and certs/short/ for the certificates).

Sequential sweep on a 16-core (32-thread) AMD Ryzen AI Max+ 395, starting with no caches (prime-product segments built during the sweep are shared by later runs — they depend only on the prime range, not the bit-length). Certificates verified by voneshot.py; the sweep stops at the first prime exceeding five minutes.

The 10¹⁰⁰ time is dominated by the discriminant scan (its only winner appears at B ≈ 4×10⁹) plus a degree-35085 class polynomial (parallel ECRT workers, OpenMP/ half-gcd root finder). The 10⁶⁰ winner is a class that would be skipped without isogeny-volcano descent (see below).

A subtlety worth knowing about: a Montgomery model exists iff 4 | #E, and additionally 8 | #E when p ≡ 3 (mod 4) — and whether it exists is an invariant of the CM class, so no root of H_D works when it fails. Rather than discard such discriminants (half the pool when p ≡ 3 mod 4), cm_method descends the 2-isogeny volcano to its floor with the classical Φ₂ (walk-to-the-floor, non-backtracking): the floor curve has cyclic 2-Sylow, its 2-torsion point is halvable, and a Montgomery model always exists. The same walk at odd primes ℓ | n₁ (E ≅ Z/n₁ × Z/n₂) makes the ℓ-Sylow cyclic, so the certificate m can use the full ℓ-power of #E instead of avoiding it (see design.md).

certs/ also holds verified certificates for the least primes above 10ⁿ for n = 55, 65, 75, 85, 95 and 105 (~1 s, ~1 s, ~7 s, ~90 s, ~30 s and ~5 min respectively), contributed along with the rows above to the challenge repo's list of one-shot ECPPs.

Verify any of them with python3 voneshot.py $(cat certs/<file>).

• gcc 13+ and GMP 6+ (the build and oneshotECPP itself).
• PARI/GP 2.x — only for the correctness test suites, not for oneshotECPP.
• Modular polynomials: a 46 MB subset is bundled (phi_files/, see INSTALL); it covers the class invariants and levels the CM method uses over the 128–384-bit range.

make test                         # classpoly vs PARI (Tests 1/2/3)
python3 ecpp/test_smooth.py       # n⁴-smoothness engine vs PARI
python3 ecpp/test_dscan.py        # discriminant scan vs PARI + brute force
./ecpp/roottest pari 256 200      # F_p root finder vs PARI polrootsmod

Makefile        setenv.sh          design.md
ff_poly_v2.0.0/   classpoly_v1.0.3/    (vendored: word-size F_p / class polynomials,
                 including the zp_poly large-p F_p[x] code: fast gcd, invariant->j)
phi_files/      (28 MB subset of modular polynomials; see INSTALL)
ecpp/           (this project: discriminant search, smoothness, root-finding,
                 invariant->j, curve assembly, oneshotECPP)
tests/          (classpoly correctness suites vs PARI)