BARRETT REDUCTION replace the division by a multiply and a shift
To compute x mod n you normally divide by n. Barrett’s trick precomputes a fixed-point reciprocal μ = ⌊2^k / n⌋ once, then estimates the quotient as q = (x·μ) >> k — a multiply and a shift — and recovers x - q·n. The estimate is off by at most one, fixed with a single subtraction. A general modular reduction that never divides, for a modulus known in advance.
THE TECHNIQUE q = (x*mu) >> k ; r = x - q*n
Reduce 5000 mod 97 with μ = ⌊2^14 / 97⌋ = 168 precomputed. The quotient estimate is a multiply and a shift; the remainder is one subtraction — no division by 97: live demo
HISTORY & CREDIT Paul Barrett, CRYPTO 1986
“The quotient estimate q is always exact.” — no. Truncating the fixed-point reciprocal makes q low by at most 1, so r = x - q·n can land in [n, 2n); one conditional subtraction of n corrects it. The bound “off by at most one” is the whole correctness argument. cited
1986 · Paul Barrett — “Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor” (CRYPTO’86): the reduction that lets a DSP with no divide instruction do RSA. the idea · approximate 1/n by the integer μ = ⌊2^k/n⌋; then ⌊x/n⌋ ≈ (xμ) >> k. vs Montgomery · Barrett works on ordinary integers (no domain conversion), Montgomery (186) works in a transformed domain — Barrett wins for a one-off reduction, Montgomery for a long exponentiation.
Both Barrett and Montgomery answer the same question — how to reduce mod n without a hardware divide — and both replace the division by a multiply plus a shift; they differ only in where the precomputation lives. Barrett 1986
RECOMMEND FOR I-13 the remainder, computed
On the canonical compiler 5000 mod 97 falls out of a multiply and a shift — >> doing the division’s job:
$ i13 run barrett.i13 # n=97, mu = floor(2^14/97) = 168, k=14
q = (5000 * 168) >> 14 = 51 -- quotient estimate: a multiply and a shift
r = 5000 - 51*97 = 53 -- 5000 mod 97 = 53, no division performed
Recommend: Barrett reduction is LIT on I-13 and the general-purpose partner to Montgomery (186) — verified 5000 mod 97 = 53 via q = (5000·168) >> 14 = 51 then 5000 - 51·97, with the shift standing in for the division. Unlike Montgomery it needs no domain conversion, so it is the right reduction for a singlex mod n against a fixed modulus — and for a language where the modulus is known, precomputing μ once turns every later reduction into a multiply and a shift. The honest caveat — the estimate is off by at most one — is one conditional subtraction.