MONTGOMERY MULTIPLICATION modular multiply with no division, only shifts
Modular multiplication’s cost is the division by n in the reduction. Montgomery’s trick: move numbers into a transformed domain (multiply by R = 2^k), where reduction mod n becomes a mask and a shift by the power of two — no division by n at all. Convert in, do all your modular multiplies cheaply, convert out. It is the reduction inside every fast RSA and ECC implementation.
THE TECHNIQUE REDC: add a multiple of n, then shift
The core is REDC(T), which computes T·R⁻¹ mod n using only & (R-1) and >> k — never dividing by n. For n=97, R=128: watch REDC reduce a product with a mask and a shift: live demo
HISTORY & CREDIT Peter Montgomery, Math. Comp. 1985
“Montgomery makes one modular multiply faster.” — not by itself. Converting in and out of Montgomery form costs a reduction each way, so a single multiply is not cheaper; it pays off across many multiplications in the same modulus (a modular exponentiation), where you convert once and reduce by shift every step. cited
1985 · Peter L. Montgomery — “Modular Multiplication Without Trial Division” (Mathematics of Computation 44): the REDC algorithm. the trick · pick R = 2^k > n, precompute n’ = -n⁻¹ mod R; then REDC(T) = (T + (T·n’ mod R)·n) / R is exact and division-by-n-free. everywhere · the standard modular-reduction in OpenSSL, GMP, and every constant-time RSA/ECC core.
The magic line adds a multiple of n (which changes nothing mod n) chosen so the low k bits become zero — then the shift is exact. You trade a hard division for an easy multiplication by the precomputed n’. Montgomery 1985
RECOMMEND FOR I-13 reduction by shift, computed
On the canonical compiler REDC reduces with a mask and a shift, no division by n — the bitwise operators doing real work:
Recommend: Montgomery multiplication is LIT and the reason I-13’s bitwise operators earn their keep — verified REDC(T) = (T + (T·n’ & 127)·n) >> 7 reduces mod 97 with only a mask and a shift (REDC(3000)=78, REDC(9700)=0), never dividing byn. For an I-13 crypto layer (RSA 050, Diffie-Hellman 035) this is the multiply to put under the modular exponentiation: convert once, then every squaring reduces by >> instead of a costly %. It is the practical companion to Barrett reduction (187) — two ways to kill the division in modular arithmetic.