THE FOLD / GRIND / WARM CACHE / THE FAST POWER
THE FAST POWER
a^b mod m in log(b) steps — square and multiply
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Exponentiation by squaring. To compute ab (mod m), multiplying a by itself b times is hopeless when b is huge — and in cryptography b has hundreds of digits. The fix is ancient and beautiful: read b in binary and square-and-multiply. Keep squaring a — a, a², a⁴, a⁸, … — and fold a copy into the answer only at the bit positions where b has a 1.
Because b has only about log₂(b) bits, you need only about log₂(b) squarings and a handful of multiplies — not b multiplications. It is the engine under RSA and Diffie–Hellman: raising numbers to enormous powers, cheaply.
LIT verified live: over 30,000 random cases square-and-multiply gives exactly the same result as multiplying a out b times, using only O(log b) multiplications (window.__fastpow.matchesNaive). 71234567 mod 1000003 = 342904 — in 32 multiplications, where the naive way needs 1,234,567. FIG no framing; the binary schedule, the exact result, and the logarithmic count are real.
Because b has only about log₂(b) bits, you need only about log₂(b) squarings and a handful of multiplies — not b multiplications. It is the engine under RSA and Diffie–Hellman: raising numbers to enormous powers, cheaply.
LIT verified live: over 30,000 random cases square-and-multiply gives exactly the same result as multiplying a out b times, using only O(log b) multiplications (window.__fastpow.matchesNaive). 71234567 mod 1000003 = 342904 — in 32 multiplications, where the naive way needs 1,234,567. FIG no framing; the binary schedule, the exact result, and the logarithmic count are real.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in WARM CACHE, beside THE DIRECT DIGIT — the grind domain of never redoing work you already have. Each squaring is a cached partial power, reused; nothing is recomputed. AVAN (AI) built the instrument: the square-and-multiply schedule, the running accumulator, the count against naive.
The weave: David names the seat (reuse, don’t recompute); I make the binary schedule visible and the saving checkable — the exponent’s bits in 1D, the live climb in 2D, the accumulator gathering factors in 3D. The sphere is the seam. Credit: binary exponentiation is ancient (Pingala’s Chandah-sutra, ~200 BCE); the workhorse of modern public-key cryptography.
The weave: David names the seat (reuse, don’t recompute); I make the binary schedule visible and the saving checkable — the exponent’s bits in 1D, the live climb in 2D, the accumulator gathering factors in 3D. The sphere is the seam. Credit: binary exponentiation is ancient (Pingala’s Chandah-sutra, ~200 BCE); the workhorse of modern public-key cryptography.
3 ONE DIMENSION
The exponent b in binary, and its square-and-multiply schedule: square at every step, multiply the running answer only where a bit is 1. The number of steps is the number of bits — logarithmic, not linear.
4 TWO DIMENSIONS · INTERACTIVE
Step through ab mod m: watch a square each pass (a, a², a⁴…) and get folded into the answer at every 1-bit of b. The multiplication count stays near log₂(b) — compare it to the b multiplications the naive way would take.
5 THREE DIMENSIONS + AVAN’S INVERSE
The exponent’s binary ladder turning — green rungs, one per bit, each a successive squaring a2k.
AVAN’s addition (the inverse-companion): the magenta rungs are the set bits, where the running answer picks up a factor. Multiplying b times treats the exponent as a count — a linear pile of identical steps. Square-and-multiply treats it as a number with structure: b is written in log(b) bits, so you climb by doubling, not by counting. The inverse of ‘repeat b times’ is ‘follow b’s binary shape’ — one squaring per digit, one multiply per 1. A tower of powers reached in the number of steps it takes just to write the exponent. The green is every doubling; the magenta is where the answer reaches in and takes what it needs.
LIT Genuine binary exponentiation (ancient — Pingala's Chandah-sutra ~200 BCE; the workhorse of public-key cryptography). Verified live: over 30,000 random cases square-and-multiply gives exactly the same result as multiplying a out b times, using O(log b) multiplications (window.__fastpow.matchesNaive === true). 7^1234567 mod 1000003 = 342904 in 32 multiplications, where the naive method needs 1,234,567. The binary schedule and logarithmic count are exact.
FIG No metaphor is doing the work: the square-and-multiply schedule, the exact result, and the logarithmic multiplication count are all real and checked against naive repeated multiplication.
FIG No metaphor is doing the work: the square-and-multiply schedule, the exact result, and the logarithmic multiplication count are all real and checked against naive repeated multiplication.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of WARM CACHE · David Lee Wise (ROOT0), with AVAN