Barrettreduksjon

Barrettreduksjon, or Barrett reduction, is a method in computational number theory for reducing a large integer modulo a fixed modulus without performing division by the modulus at runtime. The technique uses a precomputed constant mu that depends only on the modulus and the chosen representation base, enabling most of the work to be done by multiplications and shifts rather than divisions.

In a typical setting, numbers are represented in base b, often a power of two matching the machine word size. Let m be the modulus and k be the number of base-b digits of m. Define B = b^k and mu = floor(B^2 / m). For any input x with 0 ≤ x < B^2, Barrett reduction proceeds as follows: q1 = floor(x / B); q2 = q1 * mu; q3 = floor(q2 / B); r = x - q3 * m. If r ≥ m, subtract m (or apply a small fixed number of subtractions) to obtain r < m. The result r is x mod m.

Variants exist to handle values of x larger than B^2 or to integrate the method into multi-precision arithmetic pipelines. The correctness rests on mu approximating B^2 / m; the small approximation error is absorbed by the final correction step.

Barrett reduction is particularly advantageous when reducing many integers modulo the same modulus, such as in modular exponentiation or cryptographic algorithms, because the precomputation is performed once and reused. It contrasts with Montgomery reduction, which uses a different precomputation and is tailored to Montgomery-form numbers. The technique was introduced by Peter Barrett in 1986. See also modular reduction, Montgomery reduction, and modular exponentiation.