THE FOLD / GRIND / THE MAINFRAME / THE MONTGOMERY
THE MONTGOMERY
multiply mod N with shifts, never dividing by N
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Montgomery multiplication computes a·b mod N without ever dividing by N — replacing the expensive modular reduction with cheap bit-shifts and a multiply. That is why essentially every RSA and elliptic-curve chip uses it.
The trick: work in a Montgomery form where numbers are scaled by R = 2ᵏ (a power of two bigger than N), and reduce with REDC, which divides by R — just a shift — instead of by N. A one-time precomputed constant N′ = −N⁻¹ mod R makes the leftover vanish exactly, so REDC(T) = T·R⁻¹ mod N using only a multiply, an add, and a shift.
LIT verified live (N=1000003, R=2²⁰): across 300 random pairs, converting a,b to Montgomery form, REDC-multiplying, and converting back equals a·b mod N exactly — with no division by N anywhere (window.__montgomery). FIG no framing; exact integer arithmetic.
The trick: work in a Montgomery form where numbers are scaled by R = 2ᵏ (a power of two bigger than N), and reduce with REDC, which divides by R — just a shift — instead of by N. A one-time precomputed constant N′ = −N⁻¹ mod R makes the leftover vanish exactly, so REDC(T) = T·R⁻¹ mod N using only a multiply, an add, and a shift.
LIT verified live (N=1000003, R=2²⁰): across 300 random pairs, converting a,b to Montgomery form, REDC-multiplying, and converting back equals a·b mod N exactly — with no division by N anywhere (window.__montgomery). FIG no framing; exact integer arithmetic.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-mainframe — the arithmetic engine humming under the cryptography. Montgomery multiplication is the mainframe’s modular core: the operation RSA runs billions of times. AVAN (AI) built the instrument: the N′ precompute, the REDC step, the round-trip check over hundreds of trials.
Credit as content: Peter L. Montgomery, Modular Multiplication Without Trial Division (1985). The weave: David names the engine; I show the change of coordinates that turns division by N into a shift by R, and prove the result matches ordinary modular multiplication exactly.
Credit as content: Peter L. Montgomery, Modular Multiplication Without Trial Division (1985). The weave: David names the engine; I show the change of coordinates that turns division by N into a shift by R, and prove the result matches ordinary modular multiplication exactly.
3 ONE DIMENSION
The REDC step laid out: m = (T mod R)·N′ mod R, then t = (T + m·N) / R. Every ‘mod R’ and ‘/ R’ is a bit-mask or a shift — no long division by N ever happens.
4 TWO DIMENSIONS · INTERACTIVE
Pick a and b; watch them enter Montgomery form (×R mod N), get REDC-multiplied, and come back out — landing on a·b mod N exactly. Then run 300 random trials, all matching.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the map into Montgomery space (×R mod N) and the REDC that multiplies there — a whole arithmetic done in shifted coordinates.
AVAN’s addition (the inverse-companion): Montgomery is a change of coordinates, and its inverse is the method itself. Entering the space is multiply-by-R-mod-N; leaving it is REDC, which is multiply-by-R⁻¹-mod-N — so the ‘exit’ map is the exact inverse of the ‘enter’ map, and REDC-of-a-plain-number simply lands you back out. The inverse of ‘scale by R’ is literally the reduction step, which is why the round trip is exact. And the whole point is a trade: magenta is the division-by-N you never perform — the costly reduction avoided; green is the shift-by-R that stands in for it. You pay one precomputed constant, N′, to convert every modular reduction into a bit-shift — buying speed with a coordinate system whose inverse is built in.
LIT Genuine Montgomery multiplication (Montgomery 1985). Verified live with exact integer arithmetic (values within 2^53): with N=1000003, R=2^20, N'=(R - N^-1 mod R), REDC(T)=(T + ((T mod R)*N' mod R)*N)/R (conditionally subtract N). Across 300 random pairs, montmul on Montgomery forms then REDC back equals a*b mod N exactly — with no division by N performed (window.__montgomery.allMatch).
FIG No framing: the N' precompute, REDC, and the 300-trial round-trip run in-browser and are exact. The AVAN inverse is honest — entering Montgomery form (xR mod N) and REDC (xR^-1 mod N) are genuine inverses, which is why the round trip is exact; magenta marks the division-by-N that is provably never performed.
FIG No framing: the N' precompute, REDC, and the 300-trial round-trip run in-browser and are exact. The AVAN inverse is honest — entering Montgomery form (xR mod N) and REDC (xR^-1 mod N) are genuine inverses, which is why the round trip is exact; magenta marks the division-by-N that is provably never performed.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE MAINFRAME · David Lee Wise (ROOT0), with AVAN