Barrett reduction

In modular arithmetic, Barrett reduction is a reduction algorithm introduced in 1986 by P.D. Barrett.[1] A naive way of computing

c = a \,\bmod\, n. \,

would be to use a fast division algorithm. Barrett reduction is an algorithm designed to optimize this operation assuming n is constant, and a<n^2, replacing divisions by multiplications.

General idea

Let m=1/n be the inverse of n as a floating point number. Then

a \,\bmod\, n = a-\lfloor a m\rfloor n

where \lfloor x \rfloor denotes the floor function. The result is exact, as long as m is computed with sufficient accuracy.

Barrett algorithm

Barrett algorithm is a fixed-point analog which expresses everything in terms of integers. Let k be the smallest integer such that 2^k>n. Think of n as representing the fixed-point number n 2^{-k} . We precompute m such that m = \lfloor 4^k/n \rfloor. Then m represents the fixed-point number m 2^{-k} \approx (n 2^{-k})^{-1} .

Let
q = \left\lfloor \frac{m a}{4^k} \right\rfloor and
r = a - q n.

Because of the floor function, q is an integer and r \equiv a \pmod{n}. Also, if a<n^2 then r<2 n . In that case

a \,\bmod\, n = \begin{cases} r & \text{if } r<n \\ r-n & \text{otherwise} \end{cases}

Barrett algorithm for polynomials

It is also possible to use Barrett algorithm for polynomial division, by reversing polynomials and using X-adic arithmetic.

See also

Montgomery reduction is another similar algorithm.

References

  1. ↑ Barrett, P. (2006). "Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor". Advances in Cryptology — CRYPTO' 86. Lecture Notes in Computer Science 263. pp. 311–323. doi:10.1007/3-540-47721-7_24. ISBN 978-3-540-18047-0.

Sources