THE FOLD / CHEAT / THE EXPLOIT / THE BABY-STEP GIANT-STEP
THE BABY-STEP GIANT-STEP
discrete log by meeting in the middle, O(sqrt n)
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Baby-step giant-step solves the discrete logarithm — find x with gx ≡ h (mod p) — by meeting in the middle. Write x = im + j with m = ⌈√n⌉. Precompute the ‘baby steps’ g0, g1, …, gm−1 in a table, then take ‘giant steps’ h·(g−m)i until one lands in the table. It costs O(√n) time and space instead of O(n).
It is the classic generic attack on discrete-log cryptography.
LIT verified live: over 300 random (p, g, x) the recovered exponent x′ satisfies gx′ ≡ h (mod p); e.g. 2x ≡ 9 (mod 23) gives x = 5 (window.__babystepgiantstep). FIG no framing; exact.
It is the classic generic attack on discrete-log cryptography.
LIT verified live: over 300 random (p, g, x) the recovered exponent x′ satisfies gx′ ≡ h (mod p); e.g. 2x ≡ 9 (mod 23) gives x = 5 (window.__babystepgiantstep). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-exploit — the generic crack on a discrete-log secret, a way in bought by a square-root of work. Baby-step giant-step is that exploit. AVAN (AI) built the instrument: the baby-step table, the giant-step walk, the gx′≡h check.
Credit as content: Daniel Shanks (1971). The weave: David names the exploit; I lay down √n baby steps, walk giant steps until they collide, and confirm the recovered exponent reproduces h.
Credit as content: Daniel Shanks (1971). The weave: David names the exploit; I lay down √n baby steps, walk giant steps until they collide, and confirm the recovered exponent reproduces h.
3 ONE DIMENSION
The exponent x is split as im + j: the baby steps enumerate the small part j (a table), the giant steps stride by m to find the large part i. Two √n walks meet.
4 TWO DIMENSIONS · INTERACTIVE
Pick a prime, base, and target; baby-step giant-step recovers the exponent, checked by re-exponentiating.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the recovered exponent, where the two walks collide.
AVAN’s addition (the inverse-companion): you recover x by meeting in the middle. Splitting x = im + j lets you precompute all baby steps gj and then walk giant steps until one matches — √n space buys √n time instead of n. The inverse of ‘exponentiate forward’ is ‘split the unknown exponent in two and collide the halves.’ Magenta is the n exponents a brute search would try; green is the √n table and √n walk that meet. A time–memory trade cracks the log — hard only because real groups make n astronomically large.
LIT Genuine baby-step giant-step (Shanks 1971). Verified live: the meet-in-the-middle search returns an exponent x' with g^x' = h (mod p) for 300 random (prime, base, exponent) triples (window.__babystepgiantstep.recovers); 2^5 = 9 (mod 23).
FIG No framing: the baby-step table, the giant-step walk, and the g^x'=h check run in-browser and are exact. The AVAN inverse is honest — splitting x = im + j lets a sqrt(n) table and sqrt(n) walk collide, a time-memory trade recovering x without brute force; magenta is the n exponents avoided, green the collision. Hard only because real groups make n astronomically large.
FIG No framing: the baby-step table, the giant-step walk, and the g^x'=h check run in-browser and are exact. The AVAN inverse is honest — splitting x = im + j lets a sqrt(n) table and sqrt(n) walk collide, a time-memory trade recovering x without brute force; magenta is the n exponents avoided, green the collision. Hard only because real groups make n astronomically large.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE EXPLOIT · David Lee Wise (ROOT0), with AVAN