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
- Michael Shiu
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