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.

Single-word Barrett reduction

Barrett initially considered an integer version of the above algorithm when the values fit into machine words.

When calculating $a \,\bmod\, n$ using the method above, but with integers, the obvious analogue would be to use division by $n$:

func reduce(a uint) uint {
  q := a / n  // Division implicitly returns the floor of the result.
  return a - q * n
}

However, division can be expensive and, in cryptographic settings, may not be a constant-time instruction on some CPUs. Thus Barrett reduction approximates $1/n$ with a value $x/2^k$ because division by $2^k$ is just a right-shift and so is cheap.

In order to calculate the best value for $x$ given $2^k$ consider:

$\frac{1}{n} = \frac{{2^k}/{n}}{n(\frac{2^k}{n})} = \frac{{2^k}/{n}}{2^k} = \frac{x}{2^k}$

In order for $x$ to be an integer, we need to round ${2^k}/{n}$ somehow. Rounding to the nearest integer will give the best approximation but can result in $x/2^k$ being larger than $1/n$, which can cause underflows. Thus $x = \lfloor {2^k}/{n} \rfloor$ is generally used.

Thus we can approximate the function above with:

func reduce(a uint) uint {
  q := (a * x) >> k // ">> k" denotes bitshift by k.
  return a - q * n
}

However, since $x/2^k \le 1/n$, the value of q in that function can end up being one too small, and thus a is only guaranteed to be within $[0, 2n)$ rather than $[0, n)$ as is generally required. A conditional subtraction will correct this:

func reduce(a uint) uint {
  q := (a * x) >> k
  a -= q * n
  if n <= a {
    a -= n
  }
}

Since $x/2^k$ is only an approximation, the valid range of $a$ needs to be considered. The error of the approximation of $1/n$ is:

$e = \frac{1}{n} - \frac{x}{2^k}$

Thus the error in the value of q is $ae$. As long as $ae < 1$ then the reduction is valid thus $a < 1/e$. The reduction function might not immediately give the wrong answer when $a \ge 1/e$ but the bounds on $a$ must be respected to ensure the correct answer in the general case.

By choosing larger values of $k$, the range of values of $a$ for which the reduction is valid can be increased, but larger values of $k$ may cause overflow problems elsewhere.

Example

Consider the case of $n = 101$ when operating with 16-bit integers.

The smallest value of $k$ that makes sense is seven because if $2^k < n$ then the reduction will only be valid for values that are already minimal! For a value of seven, $x = \lfloor 2^k / n \rfloor = \lfloor 128 / 101 \rfloor = 1$. For a value of eight $x = \lfloor 256 / 101 \rfloor = 2$. Thus $k = 8$ provides no advantage because the approximation of $1/101$ in that case ($2/256$) is exactly the same as $1/128$. For $k$ equal to nine, $x = 512 / 101 = 5$, which is a better approximation.

Now we consider the valid input ranges for $k = 7$ and $k = 9$. In the first case, $e = 1/n - x/2^k = 1/101 - 1/128 = 27/12928$ so $a < 1/e$ implies $a < 478.81$. Since $a$ is an integer, effectively the maximum value is 478. (In practice the function happens to work for values up to 504.)

If we take $k = 9$ then $e = 1/101 - 5/512 = 7/51712$ and so the maximum value of $a$ is 7387. (In practice the function happens to work until 7473.)

The next value of $k$ that results in a better approximation is 13, giving $81/8192$. However, note that the intermediate value $ax$ in the calculation will then overflow an unsigned 16-bit value when $810 \le a$, thus $k = 7$ works better in this situation.

Multi-word Barrett reduction

Barrett's primary motivation for considering reduction was the implementation of RSA, where the values in question will almost certainly exceed the size of a machine word. In this situation, Barrett provided an algorithm that approximates the single-word version above but for multi-word values. For details see section 14.3.3 of the Handbook of Applied Cryptography.^[2]

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.
2. Menezes, Alfred; Oorschot, Paul; Vanstone, Scott. Handbook of Applied Cryptography. ISBN 0-8493-8523-7.

Sources

• Bosselaers, et al., "Comparison of Three Modular Reduction Functions," Advances in Cryptology-Crypto'93, 1993.
• W. Hasenplaugh, G. Gaubatz, V. Gopal, "Fast Modular Reduction", ARITH 18