Barrett reduction

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

$c=a{\pmod {n}}.\,$

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

Naive idea

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

$a{\pmod {n}}=a-\lfloor am\rfloor n$ where $\lfloor x\rfloor$ denotes the floor function,

assuming m was computed with sufficient accuracy.

Barrett algorithm

Barrett algorithm is a 2-adic analog which avoids the use of floating point. Assume n is odd and Let k be the smallest integer such that $2^{k}>n$. We precompute m such that $m=\lfloor 4^{k}/n\rfloor$.

Let $q=\lfloor ma/{4^{k}}\rfloor$ and $r=a-qn$. Then

$a=r{\pmod {n}}$

and if $a<n^{2}$ then $r<2n$. So $a{\pmod {n}}$ is either equal to $r$ or $r-n$

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.

Sources

• Chapter 14 of Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996. ISBN 0-8493-8523-7.
• Bosselaers, et al., "Comparison of Three Modular Reduction Functions," Advances in Cryptology-Crypto'93, 1993. [1]
• W. Hasenplaugh, G. Gaubatz, V. Gopal, "Fast Modular Reduction", ARITH 18