THE FOLD / BOSS / THE GATEKEEPER / THE MILLER-RABIN
THE MILLER-RABIN
a witness names the composite, no factor needed
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Miller–Rabin test decides whether a number is prime by interrogating witnesses. Write n−1 = 2r·d; a base a is a witness to compositeness if ad ≠ 1 and none of ad, a2d, … equals n−1 (mod n). Rabin proved that for any odd composite n > 9, at least 3/4 of the bases are witnesses — so a handful of random bases catch composites with overwhelming probability, and small fixed base sets are deterministic below known bounds.
LIT verified live: a fixed 12-base test agrees with trial division for every n below 100000, and over random odd composites the witness fraction never drops below 3/4 (window.__millerrabin). FIG the ≥3/4 density is Rabin's theorem, confirmed by exhaustive count; the deterministic agreement is a bounded exhaustive check.
LIT verified live: a fixed 12-base test agrees with trial division for every n below 100000, and over random odd composites the witness fraction never drops below 3/4 (window.__millerrabin). FIG the ≥3/4 density is Rabin's theorem, confirmed by exhaustive count; the deterministic agreement is a bounded exhaustive check.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-gatekeeper — the guard that won't let a number pass as prime unless it survives interrogation. Miller–Rabin is that gate. AVAN (AI) built the instrument: the modular squaring ladder, the witness test, the trial-division oracle, and the ≥3/4 witness-density count.
Credit as content: Gary Miller (1976) & Michael Rabin (1980). The weave: David names the-gatekeeper; I run the witness test against a trial-division oracle and count, for odd composites, exactly what fraction of bases expose them — confirming Rabin's 3/4 bound live.
Credit as content: Gary Miller (1976) & Michael Rabin (1980). The weave: David names the-gatekeeper; I run the witness test against a trial-division oracle and count, for odd composites, exactly what fraction of bases expose them — confirming Rabin's 3/4 bound live.
3 ONE DIMENSION
For a composite n, most bases a are witnesses (they expose n). Rabin: at least 3 in 4 always are. Pick t random bases and the chance all miss is ≤ 4−t.
4 TWO DIMENSIONS · INTERACTIVE
Test a number; see its witnesses vs liars, and the fixed-base verdict checked against trial division.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: primality decided by surviving witnesses.
AVAN’s addition (the inverse-companion): prove a number composite not by finding a factor but by finding a witness — a base whose modular-squaring ladder violates what a prime would force. Since ≥3/4 of bases are witnesses (Rabin), a few random ones suffice. The inverse of ‘factor it to prove it composite’ is ‘exhibit one witness — no factor needed.’ Magenta is the factorization avoided; green is the witness found. Compositeness proven without factoring.
LIT Genuine Miller–Rabin test (Gary Miller 1976; Michael Rabin 1980). Verified live: a fixed 12-base test matches trial division for every n below 100000 (window.__millerrabin.matchesTrial, bounded exhaustive), and over sampled odd composites the fraction of bases that are witnesses never falls below 3/4 — Rabin's theorem — confirmed by exhaustive per-composite count (window.__millerrabin.densityHolds; observed min ≈0.7527, the tight bound).
FIG Honestly scoped: the ≥3/4 density is Rabin's theorem confirmed by exact count, and the deterministic agreement is a bounded exhaustive check below 100000 (fixed small base sets are only provably deterministic under known bounds, not for all n). The modular-squaring ladder, the witness test, and the trial oracle run in-browser and agree. The AVAN inverse is honest — exhibiting one witness proves compositeness without producing any factor; magenta is the factorization avoided, green the witness found.
FIG Honestly scoped: the ≥3/4 density is Rabin's theorem confirmed by exact count, and the deterministic agreement is a bounded exhaustive check below 100000 (fixed small base sets are only provably deterministic under known bounds, not for all n). The modular-squaring ladder, the witness test, and the trial oracle run in-browser and agree. The AVAN inverse is honest — exhibiting one witness proves compositeness without producing any factor; magenta is the factorization avoided, green the witness found.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE GATEKEEPER · David Lee Wise (ROOT0), with AVAN