Montgomery Multiplication — REDC: dividing by R without dividing by n

REDC(T) returns T·R−1 mod n using only multiplies, a mask (mod R), a shift (÷R), and one conditional subtract. Watch the low k bits cancel so the ÷R is exact.

step 0

Montgomery setup & inputs

R = 2k16 n (odd?)13 n' = (−n−1) mod R11 check n·n' mod R15 = R−1 ✓ R² mod n9
a = 7 → Montgomery form ā = a·R mod n = 8
b = 9 → Montgomery form b̄ = b·R mod n = 1
Product to reduce: T = ā·b̄ = 8  (< n·R = 208)
mod R / low k bits ÷ R / shift result

REDC(T) step by step

REDC(T) = — = T·R−1 mod n
This is the Montgomery form of a·b mod n.
Convert out: a·b mod n = REDC(result) = —
Plain check: (a·b) mod n = —
Press Step to begin. We reduce T = ā·b̄ back to Montgomery form using REDC — no division by n.
Self-contained visualization. Montgomery requires an odd modulus n so that gcd(R, n) = 1 and n' exists. The magic constant n' makes T + m·n divisible by R, so ÷R is an exact shift. See junior.md and professional.md for the correctness proof. Try an even n to watch the construction fail (n' undefined). Try larger k (a bigger R) to see how the low-bit cancellation scales. Default n = 13, R = 16, a = 7, b = 9 reproduces the worked example in junior.md § Step-by-Step Walkthrough.