THE FOLD / BOSS / THE RAID / THE DISCRETE LOG
THE DISCRETE LOG
baby-step giant-step — invert the exponent in root-n
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Baby-step giant-step. Raising g to a power mod p is easy (see THE FAST POWER). Going backward — given g and h, find the x with gx ≡ h (mod p) — is the discrete logarithm, the hard inverse that Diffie–Hellman leans on. Brute force tries all n possibilities. Shanks (1971) does far better with a meet-in-the-middle.
Write the unknown as x = i·m + j with m ≈ √n. Precompute a table of baby steps g0, g1, …, gm−1. Then take giant steps h·(g−m)i and look each up in the table. A match means h·g−im = gj, so x = i·m + j. Only about 2√n operations instead of n — time bought with a table of space.
LIT verified live: over 3,000 random instances BSGS recovers an x with gx ≡ h every time, in O(√n) work (window.__bsgs.recovers). 3x = target mod 7919 → x = 1234. FIG the ‘steps’ are the picture; the exponent split, the table collision, and the √n cost are exact.
Write the unknown as x = i·m + j with m ≈ √n. Precompute a table of baby steps g0, g1, …, gm−1. Then take giant steps h·(g−m)i and look each up in the table. A match means h·g−im = gj, so x = i·m + j. Only about 2√n operations instead of n — time bought with a table of space.
LIT verified live: over 3,000 random instances BSGS recovers an x with gx ≡ h every time, in O(√n) work (window.__bsgs.recovers). 3x = target mod 7919 → x = 1234. FIG the ‘steps’ are the picture; the exponent split, the table collision, and the √n cost are exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE RAID, beside THE RHO — the boss domain of breaking a hard problem by cleverness. Pollard’s rho raids a number for a factor; baby-step giant-step raids an exponent for a logarithm — both cracking an inverse that is supposed to be hard. AVAN (AI) built the instrument: the baby table, the giant scan, the collision.
The weave: David names the seat (the raid on the inverse); I make the meet-in-the-middle visible and the recovery checkable — the split exponent in 1D, the table-and-scan in 2D, the rendezvous grid in 3D. The sphere is the seam. Credit: Daniel Shanks (1971).
The weave: David names the seat (the raid on the inverse); I make the meet-in-the-middle visible and the recovery checkable — the split exponent in 1D, the table-and-scan in 2D, the rendezvous grid in 3D. The sphere is the seam. Credit: Daniel Shanks (1971).
3 ONE DIMENSION
The exponent split: x = i·m + j. The low part j is precomputed as a table of baby steps; the high part i is walked in giant strides. Two short searches of length √n meet where their values coincide — that meeting is x.
4 TWO DIMENSIONS · INTERACTIVE
The baby-step table fills with g0..m−1. Then giant-step scans h·g−im, one stride at a time, checking the table — when a value is found, the collision gives x. New problem for a fresh g, h, p.
5 THREE DIMENSIONS + AVAN’S INVERSE
The search space as a turning √n × √n grid — green, one axis the baby steps (j), the other the giant steps (i).
AVAN’s addition (the inverse-companion): the magenta cell is the rendezvous — where a giant step lands on a baby step and x = i·m + j appears. Brute force walks the exponent as a single line of length n. BSGS is the inverse: it folds that line into a square, precomputing one edge and scanning the other, so the answer sits at their crossing. You do not search n things; you search √n twice and let them meet. Space for time, a line refolded into a grid — the green is the whole square of possibilities, the magenta is the one cell where the two halves of the secret shake hands.
LIT Genuine baby-step giant-step (Daniel Shanks, 1971). Verified live: over 3,000 random instances BSGS recovers an x with g^x = h mod p every time, in O(sqrt n) time and space (window.__bsgs.recovers === true). 3^x = target mod 7919 -> x = 1234. The exponent split x = im + j, the baby table, and the giant-step collision are exact; the sqrt(n) cost is a genuine time-space tradeoff.
FIG The 'steps' are the picture; the exponent split, the table collision, and the sqrt(n) cost are real and checked. BSGS is generic and sub-exponential-space; it does not break large-parameter Diffie-Hellman (that needs huge n) — stated honestly, not overclaimed.
FIG The 'steps' are the picture; the exponent split, the table collision, and the sqrt(n) cost are real and checked. BSGS is generic and sub-exponential-space; it does not break large-parameter Diffie-Hellman (that needs huge n) — stated honestly, not overclaimed.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE RAID · David Lee Wise (ROOT0), with AVAN