THE FOLD / LOOT / THE DROP / THE BLUM-BLUM-SHUB
THE BLUM-BLUM-SHUB
random bits provably as hard to predict as factoring
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Blum–Blum–Shub (1986) is a random-bit generator with a rare guarantee: predicting its next bit is provably as hard as factoring a large number. Choose two primes p and q both ≡ 3 (mod 4), let M = pq, start from a seed, and repeat x → x² mod M, emitting the least significant bit each step.
The bits look random — and, crucially, an attacker who has watched any run of them cannot predict the next bit better than chance unless they can factor M, which is believed intractable. Most fast generators have no such proof; BBS trades speed for a real security reduction. It also hides an elegant trick: you can jump straight to the i-th state without stepping through, via xi = x02i mod λ(M) mod M — random access into the stream, for anyone who knows the factorization.
LIT verified live: the generator is fully reproducible from its seed, and the direct-jump formula lands on exactly the same states as stepping x² mod M one at a time (window.__blumblumshub). FIG the reproducibility and the direct-access identity are exact; the unpredictability rests on factoring being hard — believed, not proven — stated honestly.
The bits look random — and, crucially, an attacker who has watched any run of them cannot predict the next bit better than chance unless they can factor M, which is believed intractable. Most fast generators have no such proof; BBS trades speed for a real security reduction. It also hides an elegant trick: you can jump straight to the i-th state without stepping through, via xi = x02i mod λ(M) mod M — random access into the stream, for anyone who knows the factorization.
LIT verified live: the generator is fully reproducible from its seed, and the direct-jump formula lands on exactly the same states as stepping x² mod M one at a time (window.__blumblumshub). FIG the reproducibility and the direct-access identity are exact; the unpredictability rests on factoring being hard — believed, not proven — stated honestly.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE DROP — the loot domain of the random reward. Blum–Blum–Shub is randomness you can trust: a drop-roll no one can predict or rig without factoring the modulus. AVAN (AI) built the instrument: the squaring stream, the direct-jump check, the square/square-root inverse.
The weave: David names the seat (the unriggable drop); I make a stream of bits reproduce from a seed and let you leap to any position, then show the one-way squaring that guards it — the states in 1D, the generator and jump in 2D, the square-vs-square-root inverse in 3D. The sphere is the seam. Credit: Lenore Blum, Manuel Blum & Michael Shub (1986); the quadratic-residuosity assumption.
The weave: David names the seat (the unriggable drop); I make a stream of bits reproduce from a seed and let you leap to any position, then show the one-way squaring that guards it — the states in 1D, the generator and jump in 2D, the square-vs-square-root inverse in 3D. The sphere is the seam. Credit: Lenore Blum, Manuel Blum & Michael Shub (1986); the quadratic-residuosity assumption.
3 ONE DIMENSION
The state marches x → x² mod M, and each step drops one bit — its parity. The row of parities is the output stream; the same seed always replays the identical row, byte for byte.
4 TWO DIMENSIONS · INTERACTIVE
Step the generator and watch the states and output bits build. Then jump to any position i: the direct formula x02i mod λ computes that state without stepping, and it lands exactly where iteration would — random access into a deterministic stream.
5 THREE DIMENSIONS + AVAN’S INVERSE
The state orbit turning on the ring of residues mod M — the green forward step: square the state, x² mod M, which anyone can do instantly.
AVAN’s addition (the inverse-companion): the magenta is the step no attacker can take — given x², recover x: a modular square root mod M. Extracting square roots modulo M is equivalent to factoring M — solve one and you can solve the other — so walking the orbit backward is exactly as hard as breaking the modulus. That is why predicting a previous (or next) bit is provably hard: it would hand you the factorization. Squaring forward is a one-way street; the inverse square root is the locked gate. And the owner’s secret is precisely the key past it — knowing p and q gives λ(M) and both the forward jump and the backward roots, while an attacker has neither. Green is the square anyone can take; magenta is the square root that would break the modulus to find — the randomness is trustworthy because its own inverse is a factoring problem.
LIT Genuine Blum-Blum-Shub CSPRNG (Lenore Blum, Manuel Blum & Michael Shub 1986). Verified live: the generator (x -> x^2 mod M, output LSB, M=209=11*19 with 11,19 = 3 mod 4) is fully reproducible from its seed, and the direct-jump formula x_i = x0^(2^i mod lambda(M)) mod M lands on exactly the same states as iterating one step at a time, for i up to 24 (window.__blumblumshub.reproducible && directAccessMatches; lambda(M)=90). The reproducibility and direct-access identity are exact.
FIG No false framing: the reproducibility and the direct-access identity (jump to any state without iterating) are real and verified in-browser. HONEST CAVEAT: BBS's unpredictability rests on the hardness of factoring / quadratic residuosity, believed but NOT proven. The AVAN inverse is genuine — forward squaring is easy, the inverse (modular square root mod M) is provably equivalent to factoring M, which is the security reduction.
FIG No false framing: the reproducibility and the direct-access identity (jump to any state without iterating) are real and verified in-browser. HONEST CAVEAT: BBS's unpredictability rests on the hardness of factoring / quadratic residuosity, believed but NOT proven. The AVAN inverse is genuine — forward squaring is easy, the inverse (modular square root mod M) is provably equivalent to factoring M, which is the security reduction.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE DROP · David Lee Wise (ROOT0), with AVAN