A Pomerance triple for p = 10²⁴ + 7

Solution to the sixth goal of the DANGER3 data challenge (BIRS workshop DANGER: Data, Numbers, and Geometry, April 2026):

p  = 1000000000000000000000007
A  = 38923582678463553756710
x0 = 843367907077058108520461

Verify it yourself with Sutherland's official verifier (a copy ships in this repo):

python3 src/vpp.py 1000000000000000000000007 38923582678463553756710 843367907077058108520461
# True

or check the machine-checkable Lean 4 certificate data/p24/p24_cert.lean (generated by the challenge's lean_vpp.py; paste into live.lean-lang.org).

Found 2026-06-11 after testing ~1.75×10¹⁰ candidates in 5 h 49 m on a single Apple M3 laptop (8 single-threaded workers). Full statistics in RESULT.md.

For an odd prime p, let q = ⌊√p⌋ and let k be the least integer with 2ᵏ > q + 1 + 2√q. A Pomerance triple (p, A, x₀) demands a point with x-coordinate x₀ on the Montgomery curve By² = x³ + Ax² + x over 𝔽ₚ whose order is exactly 2ᵏ: doubling the projective point (x₀ : 1) k times lands on the identity (Z ≡ 0 mod p), but the (k−1)-th double does not.

For p = 10²⁴ + 7 we have k = 40, so we need a point of order exactly 2⁴⁰ = 1 099 511 627 776. By Hasse, the curve's group order N lies within ±2×10¹² of p+1, and 2⁴⁰ must divide N — there are only three admissible group orders in the entire Hasse interval:

N = 2⁴⁰ · 909494701773    N = 2⁴¹ · 454747350887    N = 2⁴² · 227373675443

The concept comes from Carl Pomerance's analysis of how often the elliptic curve method (ECM) of factoring can succeed using only repeated doubling (paper); the challenge uses a refinement due to Sutherland.

This solution applies the search strategy that won the p = 10²²+9 and p = 10²³+117 goals (Ruehle's 2-Sylow projection base + McLain's X₁(16) refinements), patched to work for p ≡ 3 (mod 4):

1. 2-Sylow projection (Ruehle). For a candidate curve, multiply a random point by the odd part m of a candidate group order N = 2ᵏ⁺ᵛ·m. If the curve really has order N, the result lands in the 2-Sylow subgroup, and ~k doublings decide success — O(√p)-ish expected candidates overall, far better than blind sampling.

2. X₁(16) prescribed torsion (McLain). Instead of random curves, sample from the one-parameter family of Montgomery curves with a rational point of order 16 (via the Tate normal form parametrization of the modular curve X₁(16)). This forces 16 | N, concentrating the candidates on curves already biased toward large 2-power torsion — roughly a 16× hit-rate boost.

3. Successive halving + nonsplit-discriminant filter (McLain). Rather than multiplying by m and doubling up, repeatedly halve the 16-torsion point (each halving is one square-root extraction) to climb to the top of the 2-Sylow subgroup; a quadratic-character filter discards on the spot the ~half of samples whose halving chain must terminate early. Net effect measured at p23: ~10× fewer candidates than plain 2-Sylow projection.

McLain's sampler computed square roots as √n = n^((p+3)/8) with a √−1 correction, valid only for p ≡ 5 (mod 8) — and gated the X₁(16) modes to that class (both her targets were ≡ 5 mod 8). Our target 10²⁴+7 ≡ 7 (mod 8) falls outside the gate. But square roots are easier there: for p ≡ 3 (mod 4), √n = n^((p+1)/4) exactly when n is a quadratic residue.

Three sites in src/pomerance.c changed, each tagged PATCH(p3mod4): the two square-root helpers gained the p ≡ 3 (mod 4) branch, and the mode gate now admits p ≡ 3 (mod 4) (p ≡ 1 mod 8 remains unsupported). Everything else is byte-for-byte McLain's code, including her internal verifier, which re-checks any hit before reporting; benchmark and statistics modes keep their original gates.

The patch was validated end-to-end before the production run: on the prime 10000000000000000087 ≡ 7 (mod 8), the patched binary found (p, 5110488936977668321, 6955273311755638144) in 197 s, confirmed True by the official vpp.py (logs in data/val_p7/).

No supersingular or CM curves are involved — candidates are random ordinary curves with prescribed rational torsion, the same accepted technique as the p22 and p23 entries.

• 8 single-threaded worker processes (no OpenMP on Apple clang; sharding by PRNG seed instead — run_shards.sh), mode x16halvenonsplit
• Launched 2026-06-10 23:11 EDT; worker01 (seed 24104729) hit at 05:00:26 EDT on its 2,186,274,752nd accepted candidate
• Aggregate: 1.7512×10¹⁰ accepted candidates ≈ 0.0175·√p at 0.84 M/s (expected ≈ 0.07–0.1·√p from the p23 baseline — a ~1-in-5 lucky draw)
• A watch_hit.sh daemon spotted the hit, archived it to data/p24/HIT.txt, and stopped the fleet

cc -O3 -o src/pomerance src/pomerance.c          # Apple Silicon / clang
# (gcc -O3 -fopenmp ... -lm on Linux if you want the original threading)

# sanity check the toolchain on a small ≡ 7 (mod 8) prime (hit in minutes):
bash src/run_shards.sh 10000000000000000087 x16halvenonsplit 8 2000000000 1000 99991 data/test
./src/watch_hit.sh data/test &

# the real thing (expect ~a day at ~1M candidates/s; exponential luck applies):
bash src/run_shards.sh 1000000000000000000000007 x16halvenonsplit 8 50000000000 24000000 104729 data/p24
./src/watch_hit.sh data/p24 &

# verify any hit with the official verifier:
python3 src/vpp.py <p> <A> <x0>

• Challenge: Andrew Sutherland, DANGER3 (MIT) — vpp.py and lean_vpp.py are his
• Base search code: Fabian Ruehle with Claude Opus 4.6 (MIT)
• X₁(16) torsion + halving + nonsplit filter: Alexa McLain with GPT 5.5 Codex (MIT)
• p ≡ 3 (mod 4) patch, orchestration, and this result: this repository, with Claude (Fable 5), June 2026

Licensed MIT (see LICENSE), preserving upstream copyrights.