THE FOLD / BOSS / THE GATEKEEPER / THE SOLOVAY-STRASSEN
THE SOLOVAY-STRASSEN
test primality by the Jacobi symbol
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Solovay–Strassen test decides primality using the Jacobi symbol (a/n) — a generalization of the Legendre symbol computable by a fast quadratic-reciprocity recursion, without factoring n. Euler’s criterion says that for a prime n, a(n−1)/2 ≡ (a/n) (mod n) for every a coprime to n. For an odd composite, this congruence fails for at least half of all bases — so a few random bases catch composites with high probability. It was one of the first practical randomized primality tests.
LIT verified live: the Jacobi symbol equals the Legendre symbol for primes; the test matches trial division for odd n below 50000; and the composite witness fraction is always ≥ 1/2 (window.__solovay). FIG no framing; exact modular arithmetic vs a trial oracle.
LIT verified live: the Jacobi symbol equals the Legendre symbol for primes; the test matches trial division for odd n below 50000; and the composite witness fraction is always ≥ 1/2 (window.__solovay). FIG no framing; exact modular arithmetic vs a trial oracle.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-gatekeeper — the guard that admits n as prime only if Euler’s congruence with the Jacobi symbol holds for every tried base. AVAN (AI) built the instrument: the Jacobi-symbol recursion, the a(n−1)/2 ≡ (a/n) test, the trial-division oracle, and the ≥1/2 witness-density count.
Credit as content: Robert Solovay & Volker Strassen (1977). The weave: David names the-gatekeeper; I compute the Jacobi symbol by quadratic reciprocity, check Euler’s criterion against it, and confirm the verdict matches factoring — with at least half of all bases exposing any composite.
Credit as content: Robert Solovay & Volker Strassen (1977). The weave: David names the-gatekeeper; I compute the Jacobi symbol by quadratic reciprocity, check Euler’s criterion against it, and confirm the verdict matches factoring — with at least half of all bases exposing any composite.
3 ONE DIMENSION
n prime ⇒ a(n−1)/2 ≡ (a/n) (mod n) for all coprime a. n composite ⇒ at least half the a break it. The Jacobi symbol (a/n) is computed by reciprocity, no factoring.
4 TWO DIMENSIONS · INTERACTIVE
Test a number; see which bases witness compositeness via the Jacobi congruence, checked against trial division.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: primality by the Jacobi congruence.
AVAN’s addition (the inverse-companion): decide primality by whether Euler’s criterion holds with the Jacobi symbol — computable by reciprocity without factoring — since composites break it for ≥ half of all bases. The inverse of ‘factor n to test it’ is ‘check a(n−1)/2 ≡ (a/n) for a few bases — a mismatch proves composite.’ Magenta is the factorization; green is the Jacobi congruence. Compositeness by a symbol, not a factor.
LIT Genuine Solovay–Strassen primality test (Robert Solovay & Volker Strassen 1977). Verified live: the Jacobi symbol (by quadratic-reciprocity recursion) equals the Legendre symbol for primes (window.__solovay.jacobiCorrect), the a^((n−1)/2)≡(a/n) test with fixed bases matches trial division for odd n<50000 (matchesTrial), and over sampled odd composites the fraction of coprime bases that witness compositeness is ≥1/2 (minWitness).
FIG No framing: the Jacobi-symbol recursion, the Euler-criterion test, the trial oracle, and the ≥1/2 witness-density count run in-browser with exact modular arithmetic and agree. The AVAN inverse is honest — deciding primality by whether Euler's criterion holds with the Jacobi symbol (no factoring needed; composites break it for ≥half of bases) genuinely replaces factoring; magenta is the factorization, green the Jacobi congruence. Compositeness by a symbol, not a factor.
FIG No framing: the Jacobi-symbol recursion, the Euler-criterion test, the trial oracle, and the ≥1/2 witness-density count run in-browser with exact modular arithmetic and agree. The AVAN inverse is honest — deciding primality by whether Euler's criterion holds with the Jacobi symbol (no factoring needed; composites break it for ≥half of bases) genuinely replaces factoring; magenta is the factorization, green the Jacobi congruence. Compositeness by a symbol, not a factor.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE GATEKEEPER · David Lee Wise (ROOT0), with AVAN