Yagel Numbers: the Mersenne × Primorial Grid — Structure, a Lucas–Lehmer-Type Test, and Proven Primes at Scale
Abstract. We study the two-parameter family
We give that proof in Lucas–Lehmer form: a single
The original study (Revision 1.0) took the census domain
We compare the observed counts with a first-order Mertens heuristic as a model diagnostic only; it does not establish a Poisson law, an absence of exponent effects, or a limiting row constant. A marginal-product refinement from an earlier revision is withdrawn as a joint density, because shared exponent periods make its factors dependent. Exact bounded finite-sieve counts replace it, and no justified infinite prime-count constant is presently available.
Forward searches on the same machinery reach far beyond that domain. Their results are published at yagelnumbers.org as versioned data releases — a catalogue of proven primes, each backed by a certificate that replays against its own coordinates, and an index giving, per row and face, the exponent ranges in which every cell is decided. This paper states the method and scope behind them; their totals, which grow with each release, are in the releases. Every prime reported was proven, not screened, and on this grid the proof costs only a small multiple of the screen.
This is a living document. Revision 1.0 appeared October 23, 2024. The present revision reports the family's structure theory, its deterministic primality criteria, the census of both faces over the original domain, the first forward campaigns (June–July 2026), and the method behind the catalogue of proven primes, whose current contents are published as versioned data releases (§5.2). Corrections carried by this and earlier revisions are collected in the scientific errata at the end, together with a statement of what each claim below does and does not establish.
1. Introduction
Mersenne numbers
Fix
The construction removes divisibility by every prime up to the base: the primorial coefficient kills the primes below
- row
: , the Mersenne numbers; - column
: , the primorial numbers, whose primes are the primorial primes studied since Dubner [7] and Caldwell–Gallot [8].
Both "constants" in (1) are dictated by the prime sequence itself; the family has no free parameters and is indexed purely by the lattice point
Notation and nomenclature. Following the convention of Lucas sequences and Chebyshev polynomials, we call
What is new here, and what is not. Numbers
This paper presents the family from three angles.
Structure (§2). The sieve property is maximal; the interior admits no algebraic factorization in the exponent (a Capelli-type lemma), so every lattice cell is a live candidate — in sharp contrast to the Mersenne row, where composite exponents are disqualified; and both neighbors
A deterministic test (§3). Because
Statistics and computation (§4–5). Over the census domain of the original study (
Throughout, we are explicit about what the family does not offer (§6): the test, like Lucas–Lehmer, is
2. Structure of the grid
2.1 The maximal small-prime sieve
Proposition 1. For every prime
Proof. If
The coefficient
This is the strongest clean congruence sieve available for the base: an integer
which is the precise form of the intuition that the construction "amplifies" prime density (explicit estimates for (2) in Rosser–Schoenfeld [11]); §4 tests it against the data.
2.2 Every cell is live: no algebraic exponent filter
The Mersenne row loses all composite exponents to the identity
Lemma 2. For
Proof. Up to a nonzero scalar, the reciprocal polynomial is
So no polynomial identity in
a shifted arithmetic progression in
Two honest caveats. Lemma 2 rules out polynomial identities, not covering systems: a hypothetical far row could still be Sierpiński–Riesel-style barren by a finite set of primes covering all residues (3). Two facts constrain that possibility.
Lemma 2′. For
Proof. A covering prime has
In particular the "trivial" Riesel exclusion
2.3 Both neighbors factored
The central object of cell
and for both, the adjacent number is fully factored:
3. A Lucas–Lehmer-type test for every row
Throughout this section
, so iff and iff : multiply by and use that a field has no nonzero nilpotents. Meanwhile iff with , allowing either V sign. divides : Frobenius fixes the roots in the split case and interchanges them otherwise.
Because
Theorem 3 (one-ladder test). Let
so that
then
Proof. For each prime
For prime N the norm-one group has order M=N+1 and is cyclic. Exclude ±1; inversion pairs its remaining M−2 elements into admissible traces. The p-th power subgroup contains M/p elements including ±1 (p odd), leaving M/p−2 bad elements. Uniform admissible trace residues therefore succeed with
Parity also gives
Remarks.
- Classical edge. For N=2^n−1, n=1 gives 1 and n=2 gives 3. Composite n>1 factors N. For prime n≥3 the classical Lucas–Lehmer theorem starts at 4, iterates x²−2 exactly n−2 times and tests for zero modulo N. Arbitrary Jacobi-admissible seeds do not supply an unconditional iff test. The minus-two V condition is a sufficient order certificate; its converse needs the appropriate seed theorem, separately from the odd-p argument.
- Certificates and retries. Under the theorem's hypotheses, a failure of (i) witnesses compositeness, a proper gcd exposes a factor, and gcd=N is inconclusive. Sequential seed retries have no proved expectation here.
- Below the threshold. The regime
— equivalently by the prime number theorem — covers all but an initial segment of each row ( ; a candidate at has 179 digits). Below it the same machinery applies with more factored primes of carried until the certified part exceeds (Brillhart–Lehmer–Selfridge [1]); at most short ladders.
- Cost. The ladder spends
multiplications per step and steps: about multiplications total, versus squaring-equivalents for one Fermat test — a proof for roughly the price of three PRP tests, at the same bit complexity as Lucas–Lehmer. Mersenne's modular reduction is inherited as well, in radix (Proposition 4 below); its constant is the bit-length of .
- Empirical validation. An implementation re-proved all 476 dataset primes in the one-ladder regime and rejected 100 composite controls with zero disagreements; seed retries were observed; this does not verify a random-seed runtime law. At scale, the ladder proved the
-digit prime of §5 in 17.7 s (single seed, ) on commodity hardware — faster in practice than the equivalent -sequence BLS routine (55.6 s).
- Gcd-free form (Theorem 3′). Let
be the minimal polynomial of , (degree , integer coefficients; , ), so that and . Under the hypotheses of Theorem 3, is prime iff for any seed that is not a -th power: condition (i) is then automatic, a seed that is a -th power shows itself as (and ), and every other outcome is an exact compositeness witness. The proof is that of Theorem 3 with " is a primitive -th root of unity modulo every prime factor " read off from . This is the shape of Lucas–Lehmer: gives " ", and on row ( ) the test reads iterate from and demand the penultimate value be . Moreover is admissible on every cell with , since and give . Validated with zero disagreements on every cell with for , on all dataset primes to 1500 digits, and on row 2 to .
Prior art. Explicit Lucas–Lehmer-type criteria for numbers
3.1 Modular reduction in radix
Mersenne's remaining arithmetic advantage was, until now, the shift-and-add reduction modulo
Proposition 4 (fold at
In radix
Proof.
Remark (Montgomery form). Equivalently, with radix
The objection recorded in Revision 2.0 — that folding requires the dense constant
4. Statistics of the grid
The domain of this section. Everything in §4 is computed over one fixed domain, the census domain of the original study (Revision 1.0, 2024): orders
The domain is completely decided. On the minus face it holds 482 primes. Each is proven: it carries a stored certificate that replays against its own coordinates under the criteria of §3, or trial division below
Except where stated, counts are taken over the window 100–5,000 digits, wide enough that boundary effects and the heuristic's small-

4.1 A first-order model for the census counts
The correct null model for a family satisfying Proposition 1 is not the bare prime number theorem but PNT conditioned on the built-in sieve: a candidate of size
Result. Over the census domain restricted to
A pleasant closed form follows from
independent of
Dependent exponent sieves. For each explicit prime q>p, divisibility excludes at most one phase modulo ord_q(p). These periods share factors. For h=2,p=3,Q={5,7}, minus excludes 1 mod 4 and 4 mod 6: seven of twelve exponents survive. Plus excludes 3 mod 4 and 1 mod 6: eight survive. The marginal-independence product is 5/8 for both and is therefore not the joint density. Dividing exact survivals by (1−1/5)(1−1/7) gives finite corrections 245/288 and 35/36, versus the baseline 175/192.
Exact rational period counts, and explicit finite-window counts with their phase residues, are computed directly rather than estimated from a product; the earlier numeric product is retained only as an explicitly named marginal-independence baseline. Divisibility by

4.2 The Mersenne edge is different in kind — measurably
Row
4.3 Prime exponents: no advantage visible in this domain
Lemma 2 says no exponent is disqualified algebraically. Whether prime exponents are nonetheless favored is a separate, empirical question. Split every interior cell of the census domain (
| exponent | cells | observed | expected | |
|---|---|---|---|---|
| prime | 20,846 | 108 | 108.9 | |
| composite | 125,790 | 345 | 375.6 |
The expectation-normalized rate ratio (prime exponents : composite exponents) is
4.4 Cells prime on both faces
When both faces of a cell are prime,
the largest being
How many a heuristic expects, and where the heuristic stops. Both faces of a cell avoid every prime
Summed over
Over the 100–5,000-digit window in which §4.1 operates, (6) gives 3.07 and the census contains 3 — at
Row
4.5 The plus face
The second kind
The sieve-adjusted model of §4.1 draws no distinction between the two faces, and that prediction was registered before the plus face was swept. Over the same grid (
The sweep also doubled the family's inventory of proven primes in a single computation, which is §2.3 in practice: every candidate the sweep turned up was carried through to a certificate in the same pass, so the sweep's output is a list of theorems rather than a list of leads. The largest members of the plus-face census are

4.6 Limiting density: an open question
Mertens' theorem gives
Two approaches do not settle this. Simulating a generic coefficient changes the probability space, so it answers a different question. Comparing a heuristic with the same counts that suggested it cannot calibrate its uncertainty. A prospective test would need a census block reserved in advance and left untouched; no such holdout is claimed here.
5. Searching at scale
The properties of §2–3 assemble into a pipeline in which discovery and proof are the same pass:
- Sieve. For fixed
, mark exponents killed by primes via the rolling recurrence against the target residues of (3) — one pass per , both faces simultaneously if desired. - PRP. Survivors take one Fermat test base 2 (the theoretical minimum: one modular exponentiation), then a BPSW check.
- Certificate. A survivor of step 2 is a candidate, not yet a prime. Theorem 3 (or its Pocklington mirror on the
face) is then attempted against it, at the cost of step 2; in the one-ladder regime that is a single ladder with a seed that must succeed, and below the regime it is the multi-factor argument of Remark 3. A value enters the record only when the applicable criterion returns a certificate, and that certificate is stored and replayed. What the grid buys is that step 3 is always available and cheap, never that step 2 already settled the question.
A cost identity parallels (4): at sieve depth
5.1 The first forward campaigns (June–July 2026)
These are campaign results, not census results. The searches below target chosen rows and large exponents; they sample no domain exhaustively and are never pooled with the counts of §4. Each value listed was carried from candidate to certificate in the same pass, and is listed only because that certificate succeeded. The first forward campaigns ran in June–July 2026 on a commodity 8-core desktop with GMP arithmetic and produced:
| number | digits | face | note |
|---|---|---|---|
| 18,664 | largest of these campaigns; first known prime in row | ||
| 11,912 | largest minus-face prime of this campaign; exponent | ||
| 10,988 | |||
| 10,263 | exponent | ||
| 6,691 | |||
| 6,230 | |||
| 5,286 | |||
| 5,076 | |||
| 5,047 | exponent | ||
| 5,000 | largest of the |
The first prime in rows beyond
the latter found after 856 Fermat tests (
Proving times illustrate Remark 4: the
5.2 The catalogue and its releases
§4 is a census over one fixed domain and §5.1 is one pair of campaigns. Neither is the project's accumulated record, which grows with every search and is therefore not restated here. It is published as two versioned data releases, and a figure drawn from them should be cited with the version stamp the files carry.
The catalogue of proven primes (yagelnumbers.org/primes, machine-readable at yagelnumbers.org/data/primes.json) lists a value only when it carries a stored certificate that replays against its own coordinates. The criteria are the two of §3 and §4.5 — Lucas
The index (yagelnumbers.org/data/index.json) records, for each row and face, the exponent ranges in which every cell is decided — each prime by its certificate, every other cell by a compositeness witness of the kinds described at the head of §4. Inside such a range a cell that is not a listed prime is composite because it was witnessed, not because it is absent from the list; outside every such range, and with no certificate of its own, a cell is unknown. The calculator at yagelnumbers.org/datasets answers from the same rule, and reports
What a count of primes is not. A total of proven primes is not a claim about the regions they were found in. Much of the catalogue comes from targeted searches over chosen rows and exponent windows, and a prime found at one exponent says nothing about its neighbors; coverage is what the index states, range by range, and nothing more.
6. What the grid is, and is not
It is not a complexity breakthrough, and its test is not new. Per candidate, Fermat, Miller–Rabin, Lucas–Lehmer, and Theorem 3 are all
It is the canonical two-parameter interpolation between the Mersenne and primorial families, with four universal gifts: a maximal built-in sieve (Proposition 1), polynomial irreducibility in the interior (Lemma 2) and no cheap coverings (Lemma 2′), a certificate for every prime ever found in it (Theorem 3 and its mirror) — the property that distinguishes it inside its genus, where certificates exist only when the coefficient happens to factor — and Mersenne's linear-time reduction in its own radix (Proposition 4). Its finite statistics motivate further study but establish neither a Poisson process nor limiting row constants. And the evidence has a boundary worth stating plainly: every prime reported here was proven, and its certificate re-checked, by this project's own implementations. Replay in a second system covers a sample of the catalogue, not all of it, and external recertification by an independent party has not been carried out. No proof archive or independent verifier is published.
Open problems.
- Optimality of Proposition 4: can the product by
be amortized so that the reduction is with a constant independent of the row — or is the truth? And, practically, a weighted-transform implementation for (rows ), where current production code falls back to generic arithmetic. - Covering systems: Lemma 2′ excludes periods 1 and 2 and no row
is covered by the primes to , but whether any row is barren remains open; a proof would need control of the prime factors of above . - Deterministic seeds: the
-th-power condition of Theorem 3 is resolved by reciprocity for [13–15, 18]; on the grid the coefficient is fully known modulo everything, so an explicit seed per row may be provable for all . - The
and frontiers: the primorial-prime column is classical [7, 8]. Beyond the census domain, the smallest prime exponent of a row is known only where the index (§5.2) records every smaller exponent as decided; the first primes found beyond (§5.1) are not claimed to be the smallest. - Twin records within the family: because both members are provable, the grid is a natural venue for large proven twins beyond the 476-digit pair of §4.4 — though at the twin top-twenty threshold of September 2026 (71,298 digits) the expected yield per million cells is below
.
Scientific errata
Corrections are recorded here rather than applied silently. The historical PDF of Revision 1.0 is preserved uncorrected; it is not the current edition.
Revision 2.1 (September 2026) — census errata. A BPSW re-test of every cell of the 2024 census found six values it had recorded as composite that are in fact prime:
Revision 2.2 (September 2026) — three errors in Revision 2.1.
- A product of marginal survival factors was treated as a joint density. Exponent periods modulo different primes share factors, so the factors are dependent and their product is not the survival density. §4.1 now gives exact finite-sieve counts instead, and the refined fits and their
-scores that rested on the product are withdrawn. - The
-sequence argument used a root ratio in place of a root. Modulo 7 with one has while , so the ratio does not carry the order argument. §3 now works with itself. - The exact seed-success fraction omitted the excluded traces. The corrected count is
, not ; see the proof of Theorem 3.
Revision 2.3 (September 2026).
- Figure 4 is withdrawn. It plotted per-row products of marginal survival factors as though they were estimates of prime-count constants. Following erratum 1 above, those products are a baseline computed under an independence assumption that does not hold, they have no established coverage, and no limiting constant is claimed for them. The figure is removed rather than relabelled; the open question it was meant to illustrate is stated plainly in §4.6 and its research source is retained with the project's records.
- Historical counts are now reported with their domain. §4's statistics are a census result over
to 5,000 digits; §5's records are the July 2026 campaign. Neither is the current project catalogue, which is larger and is published separately. Earlier revisions printed these numbers without always distinguishing them. - The plus-face census total is corrected from 470 to 484. The 2026 sweep recorded 470 primes. Fourteen further plus-face primes in the same domain, all of 1 to 5 decimal digits at
and below the exponent at which the sweep began, were established afterwards by the twin companion scan and by bounded trial division. The statistical window of §4.5 (100–5,000 digits) contains none of them, so the fit reported there is unchanged.
Revision 2.4 (September 2026). Five places where Revision 2.3 claimed more than the evidence behind it. Each surfaced on checking the text against the published index and calculator.
- The census domain's size was wrong, and the value 1 was counted as composite. The domain as defined —
, — contains 163,294 minus-face cells, from to . The figure 163,259 printed in earlier revisions is the 2024 sweep's stored extent, which falls 1 to 3 exponents short of the cap on some rows; the 35-cell tail was settled separately in 2026. Within the domain, is neither prime nor composite and had been carried inside the composite total; the composite count is 162,811, and for the 2024 sweep alone 162,776. - Reported coverage was described as a settled classification. The 482 minus-face primes and the 484 plus-face primes are proven. The classifications over the rest of the domain come from the sweeps that covered them — the Revision 2.1 erratum above is itself a case of six of them being wrong — and the published index declares a cell composite only where completion evidence exists, answering unknown elsewhere. §4 now says so, and no longer speaks of the census "settling" its domain. (Revision 2.5 corrects how §4 said it.)
- Screening was described as proof. §5's pipeline said a survivor of the PRP stage is "immediately proven" by Theorem 3, and the abstract that searching and proving are the same act. A survivor is a candidate; the criterion is then attempted and may need a different seed, or the multi-factor form below the one-ladder threshold. Relatedly, the grid supplies the factored-neighbor hypothesis at every cell by construction, not every hypothesis of the criteria; the abstract and the site said the latter.
- An uncalibrated interval was reported as a 95% interval. §4.1 states that the Poisson reference is not calibrated here because the exponent sieves are dependent. §4.3 nonetheless attached nominal 95% coverage to a rate-ratio interval and read it as detecting no effect. The interval is retained as a conditional calculation with no coverage claim, and the section no longer asserts an absence of effect.
- Appendix A promised implementations that are not distributed. It said reference implementations accompany the data; the availability section, correctly, says the code is not published. Appendix A is a specification to reimplement from.
Revision 2.5 (September 2026). Three corrections, all of them to statements Revision 2.4 introduced or left standing.
- An expected twin count that could not be reproduced from its own specification. §4.4 reported a sieve-adjusted Hardy–Littlewood expectation of
pairs against 22 observed, and read the gap as indistinguishable from chance. The figure dates from a July 2026 working note whose summand, limits and treatment of row 1 were never published, and it cannot be recovered from the paper as written; the same note records that its model gave row 1 about 3.5 pairs, where algebra permits exactly one. The expectation is withdrawn and replaced by (6), a bounded sum over a stated domain with row 1 excluded on algebraic grounds and recomputable from the specification printed with it. It is numbered (6), not (5): (5) was the row-constant product withdrawn in Revision 2.2 and that number is not reused. The sum comes to 24.31 over the whole domain at against 21 observed there — printed as a diagnostic, since two of its terms exceed 1 and 87% of it comes from cells below 100 digits — and to 3.07 against 3 observed in the 100–5,000-digit window. The uniform-residue assumption behind it is now stated where it is used. No inference from the comparison is offered. - Historical classifications were written as current composite declarations. Revision 2.4 said the remaining cells "are declared composite on probabilistic screening, which is not the same grade of evidence". That misplaces the uncertainty. A Fermat or Miller–Rabin test that produces a witness decides compositeness outright — the doubt is over execution, coverage and the association of a recorded verdict with a cell, not over the mathematics. The abstract and §4 now say that, exclude
explicitly, and describe the 162,811 as cells outside the proven-prime list carrying the sweeps' classifications. - A sentence in §4.3 asserted more than the section could support. "Only a reference with calibrated coverage could do the latter" is false as stated: calibrated coverage would not by itself establish the absence of an effect. The sentence is removed; the limited conclusion before it stands.
One further change was an addition rather than a correction: §5.2 gave a dated summary of the current catalogue, which earlier revisions had left entirely to the website, so that the paper no longer reported June–July 2026 as though it were the present state. Revision 2.6 replaces that summary with a pointer to the versioned releases.
Revision 2.6 (September 2026). The paper no longer restates figures that change with the dataset, and three statements are brought up to date.
- The census domain is completely decided. Revisions 2.4 and 2.5 described the census cells outside the prime lists as carrying the 2024 sweep's classifications, and said the index answered unknown where it could not vouch for them. Every cell of the domain on both faces, save
, has since been witnessed composite from its own coordinates or, for the primes, certified, and the index declares each verdict. §4 and the abstract now state the domain as a complete enumeration and name the kinds of witness; the six false composites of the Revision 2.1 erratum are the reason the verdicts were re-derived rather than carried over. - Current catalogue figures are withdrawn from the paper. Revision 2.5 added to §5.2 a dated summary of the catalogue — its totals, the largest primes and a verified-coverage share of 0.25%. The share was overtaken within days, and the totals change with every search. §5.2 now states how the catalogue and the index are built and what they declare, and the figures themselves are published only in the versioned data releases. The paper's remaining figures are results over the fixed census domain, the dated campaigns of §5.1, and model quantities recomputable from their stated specifications.
- A campaign record was described as the minus face's largest prime. §1 called
, of digits, the largest prime of the minus face; it was the largest minus-face prime of the June–July 2026 campaigns, and larger minus-face primes were already catalogued. §1 now says so.
What the claims below establish
| Claim | Type and hypotheses | Support | What it does not establish |
|---|---|---|---|
| Maximal built-in sieve, minimal coefficient | Theorem; positive coefficient, prime base, | Proposition 1 | Uniqueness among multiples of the primorial |
| Irreducibility in the exponent | Theorem; squarefree | Lemma 2, by Eisenstein | Absence of numerical coverings; infinitude of primes in a row |
| One-ladder certificate | Theorem; | Theorem 3 | Anything about a seed that fails (ii); the classical |
| Seed success fraction | Exact finite count; | Norm-one inversion pairs | A runtime law for sequential seed search, which is not uniform |
| Finite sieve counts | Exact counts over a stated period or window | §4.1 | An infinite prime-count constant |
| Row-count comparisons | Retrospective model diagnostics over a dated domain | §§4.1–4.5 | A Poisson law; calibrated uncertainty under dependent exponents |
| Limiting prime counts | Open | §4.6 | No limiting constant is claimed |
| Catalogue proof methods | Recorded computational outcomes | The published catalogue | A published proof archive, or complete independent recertification |
| Census domain verdicts | Complete enumeration of a fixed domain: a replayed certificate for each prime, a compositeness witness for every other cell but | §4, the published index | Anything outside the domain; checks of the witnesses by a party other than this project |
| Twin-pair expectation | Heuristic sum over a stated domain, row 1 excluded by algebra | §4.4, eq. (6) | A calibrated expectation; below 100 digits the model returns probabilities above 1 |
| Catalogue and coverage | Versioned data releases, not restated in this paper | §5.2, the published files | Exhaustiveness beyond the ranges the index declares; a count of primes is not coverage |
Data and code availability
What a reader can obtain today. The catalogue of proven primes is published at yagelnumbers.org/data/primes.json, giving for each prime its order, exponent, face, digit count and the criterion its proof used. The per-order primality index, which carries the settled exponent ranges behind the composite verdicts, is at yagelnumbers.org/data/index.json. Any individual value can be recomputed and looked up at yagelnumbers.org/datasets. Each file carries a version stamp. The catalogue and the index grow with every search, so this paper does not copy their totals; a figure taken from them should be cited with the version it was read from.
What is not published. The certificates themselves — the witness data for each proof — the compositeness witnesses, and the search, proving and analysis code are held with the project and are not distributed. A reader therefore cannot re-run a proof from published material alone, and the results here rest on this project's own implementations. Appendix A specifies the algorithms in enough detail to reimplement them independently, which is the only route to a reader-side check at present.
The paper (text and figures), the catalogue and the dataset are released under the Creative Commons Attribution 4.0 license (CC BY 4.0) — reuse freely with attribution.
Acknowledgments
This work was carried out with AI assistance throughout: in the computation, in the verification tooling, in drafting, and in review. Every numerical claim in this paper is backed by a script that recomputes it. The mathematical responsibility for the results, and for the corrections recorded in the errata, is the author's.
Appendix A. Algorithms
The pseudocode below is the general form of the implementations actually used (Python, arbitrary-precision via GMP). The implementations themselves are not distributed — see Data and code availability — so this appendix is a specification to reimplement from, not a pointer to code a reader can obtain. V(c, P, N) denotes the
Algorithm 1 — one-ladder certificate for
function OneLadder(h, p, n):
N <- h * p^n - 1
for P in 3, 4, 5, ...: # seed search
D <- P^2 - 4
if gcd(D, N) is a proper divisor: return COMPOSITE
if Jacobi(D, N) != -1: continue
s <- V(h, P, N) # seed V_h
repeat n times:
prev <- s
s <- V(p, s, N) # V_m -> V_{p*m}
if s != 2 (mod N): return COMPOSITE # exact
g <- gcd(prev - 2, N)
if g == 1: return PRIME # certificate
if g < N: return COMPOSITE # factor found
# g == N: seed was a p-th power (inconclusive; no sequential probability claim) - next P
For prev == -2 (mod N) — the Lucas–Lehmer(–Riesel) form. Below the one-ladder threshold, run the same ladder for each carried prime
Algorithm 2 — proven search over a row (§5; either face).
function HuntRow(k, n1, n2, sieve limit L, face e in {-1,+1}):
h <- p_{k-1}# ; p <- p_k
alive[n1..n2] <- true
for each prime q in (p_k, L]: # sieve: shifted APs (3)
t <- -e * h^{-1} mod q # p^n = t (mod q) => q | h p^n + e
r <- p^{n1} mod q
for n = n1..n2:
if r == t and h*p^n + e > L^2: alive[n] <- false
r <- r * p mod q
for n = n1..n2 where alive[n]:
N <- h * p^n + e
if 2^{N-1} != 1 (mod N): continue # Fermat, base 2
if not BPSW(N): continue # PRP confirmation
prove: e = -1 -> Algorithm 1 (N+1 side)
e = +1 -> Pocklington on N-1 # same ladder economics
record proven prime (k, n, e)
Algorithm 3 — first prime of a row (§5): iterate gcd(N, Q#) where Q# = product of all primes <= 10^5 in place of the sieve (deciding exactly when the gcd equals
References
[1] J. Brillhart, D. H. Lehmer, J. L. Selfridge, New primality criteria and factorizations of
[2] H. Riesel, Prime Numbers and Computer Methods for Factorization, 2nd ed., Birkhäuser, 1994.
[3] M. A. Morrison, A note on primality testing using Lucas sequences, Math. Comp. 29 (1975), 181–182.
[4] H. C. Pocklington, The determination of the prime or composite nature of large numbers by Fermat's theorem, Proc. Cambridge Philos. Soc. 18 (1914–16), 29–30.
[5] Ö. J. Rödseth, A note on primality tests for
[6] S. S. Wagstaff, Jr., Divisors of Mersenne numbers, Math. Comp. 40 (1983), no. 161, 385–397.
[7] H. Dubner, Factorial and primorial primes, J. Recreational Math. 19 (1987), no. 3, 197–203.
[8] C. K. Caldwell, Y. Gallot, On the primality of
[9] S. Lang, Algebra, 3rd ed., Springer GTM 211, 2002 (Theorem VI.9.1).
[10] G. H. Hardy, J. E. Littlewood, Some problems of 'Partitio numerorum'; III, Acta Math. 44 (1923), 1–70.
[11] J. B. Rosser, L. Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94.
[12] H. C. Williams, The primality of
[13] W. Bosma, Explicit primality criteria for
[14] P. Berrizbeitia, T. G. Berry, Cubic reciprocity and generalised Lucas–Lehmer tests for primality of
[15] P. Berrizbeitia, T. G. Berry, Biquadratic reciprocity and a Lucasian primality test, Math. Comp. 73 (2004), 1559–1564.
[16] A. Stein, H. C. Williams, Explicit primality criteria for
[17] J. M. Grau, A. M. Oller-Marcén, D. Sadornil, A primality test for
[18] Y. Deng, D. Huang, Explicit primality criteria for
[19] A. Jakhar, M. K. Ram, A primality test for
[20] J. M. Grau, A. M. Oller-Marcén, D. Sadornil, A primality test for
[21] H. G. Diamond, J. Pintz, Oscillation of Mertens' product formula, J. Théor. Nombres Bordeaux 21 (2009), no. 3, 523–533.