A Cascade Sieve for Sophie Germain Primes and Cunningham Chains

We present a two-phase cascade pipeline for discovering Sophie Germain primes and Cunningham chains: (1) find all primes up to 2N+1 using a segmented sieve with modular pre-filtering, and (2) use hash or packed-bitset lookup to identify Sophie Germain primes and Cunningham chains in O(1) time per prime. We state explicit necessary conditions for candidate survival — with explicit treatment of the small-p boundary — so that no prime is ever eliminated, and we prove the overall pipeline complete and exact (zero false positives, zero false negatives). The principal contribution is methodological: the two-phase decoupling replaces O(log³ N) Miller–Rabin testing of 2p+1 with O(1) membership queries, and the cascade pre-filters eliminate 95–99.5% of candidates before the expensive sieve stage. We validate the framework empirically to N = 10¹⁰, finding 26,567,949 Sophie Germain primes, and tabulate the Cunningham chain distribution to N = 10⁹, where the longest chain has length 7, beginning at p₁ = 1,122,659. Sophie Germain prime density decays smoothly and is consistent with the Bateman–Horn Conjecture to within 6.8%.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-14
DOI
https://doi.org/10.5281/zenodo.24224335
Primary Topic
Analytic Number Theory Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

A Cascade Sieve for Sophie Germain Primes and Cunningham Chains

Michael Shiu
Zenodo (CERN European Organization for Nuclear Research)
Analytic Number Theory Research
preprint

A Cascade Sieve for Sophie Germain Primes and Cunningham Chains

Michael Shiu
preprint en

Abstract

We present a two-phase cascade pipeline for discovering Sophie Germain primes and Cunningham chains: (1) find all primes up to 2N+1 using a segmented sieve with modular pre-filtering, and (2) use hash or packed-bitset lookup to identify Sophie Germain primes and Cunningham chains in O(1) time per prime. We state explicit necessary conditions for candidate survival — with explicit treatment of the small-p boundary — so that no prime is ever eliminated, and we prove the overall pipeline complete and exact (zero false positives, zero false negatives). The principal contribution is methodological: the two-phase decoupling replaces O(log³ N) Miller–Rabin testing of 2p+1 with O(1) membership queries, and the cascade pre-filters eliminate 95–99.5% of candidates before the expensive sieve stage. We validate the framework empirically to N = 10¹⁰, finding 26,567,949 Sophie Germain primes, and tabulate the Cunningham chain distribution to N = 10⁹, where the longest chain has length 7, beginning at p₁ = 1,122,659. Sophie Germain prime density decays smoothly and is consistent with the Bateman–Horn Conjecture to within 6.8%.

Zenodo (CERN European Organization for Nuclear Research)
Analytic Number Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon