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 am\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 $m$ given $2^{k}$ consider:

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

In order for $m$ 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 ${\displaystyle m/2^{k}}$ being larger than $1/n$, which can cause underflows. Thus ${\displaystyle m=\lfloor {2^{k}}/{n}\rfloor }$ is generally used.

Thus we can approximate the function above with:

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

However, since ${\displaystyle m/2^{k}\leq 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 * m) >> k
  a -= q * n
  if n <= a {
    a -= n
  }
  return a
}

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

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

Thus the error in the value of q is ${\displaystyle 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 ${\displaystyle a\geq 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, ${\displaystyle m=\lfloor 2^{k}/n\rfloor =\lfloor 128/101\rfloor =1}$. For a value of eight ${\displaystyle m=\lfloor 256/101\rfloor =2}$. Thus $k=8$ provides no advantage because the approximation of ${\displaystyle 1/101}$ in that case (${\displaystyle 2/256}$) is exactly the same as ${\displaystyle 1/128}$. For $k$ equal to nine, ${\displaystyle m=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 ${\displaystyle 81/8192}$. However, note that the intermediate value $ax$ in the calculation will then overflow an unsigned 16-bit value when $810\leq a$, thus $k=7$ works better in this situation.

Proof for range for a specific k

Let $k_{0}$ be the smallest integer such that ${\displaystyle 2^{k_{0}}>n}$. Take ${\displaystyle k_{0}+1}$ as a reasonable value for $k$ in the above equations. As in the code snippets above, let

• ${\displaystyle q=\left\lfloor {\frac {ma}{2^{k}}}\right\rfloor }$ and
• $r=a-qn$.

Because of the floor function, $q$ is an integer and $r\equiv a{\pmod {n}}$. Also, if ${\displaystyle a<2^{k}}$ then $r<2n$. In that case, writing the snippets above as an expression:

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

The proof that $r<2n$ follows:

If ${\displaystyle a<2^{k}}$, then

${\displaystyle {\frac {a}{2^{k}}}\cdot (2^{k}\mod n)<n}$

Since ${\displaystyle n\cdot {\frac {ma\mod 2^{k}}{2^{k}}}<n}$ regardless of $a$, it follows that

${\displaystyle {\frac {a\cdot (2^{k}\mod n)}{2^{k}}}+n\cdot {\frac {ma\mod 2^{k}}{2^{k}}}<2n}$

${\displaystyle a-\left(a-{\frac {a\cdot (2^{k}\mod n)}{2^{k}}}\right)+{\frac {(n\cdot (ma\mod 2^{k}))}{2^{k}}}<2n}$

${\displaystyle a-\left(\left\lfloor {\frac {2^{k}}{n}}\right\rfloor \cdot {\frac {na}{2^{k}}}\right)+{\frac {(n\cdot (ma\mod 2^{k}))}{2^{k}}}<2n}$

${\displaystyle a-{\frac {mna}{2^{k}}}+{\frac {(n\cdot (ma\mod 2^{k}))}{2^{k}}}<2n}$

${\displaystyle a-\left({\frac {ma-(ma\mod 2^{k})}{2^{k}}}\right)\cdot n<2n}$

${\displaystyle a-\left\lfloor {\frac {ma}{2^{k}}}\right\rfloor \cdot n<2n}$

$r<2n$

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