Barrett reduction

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

${\displaystyle c=a\,{\bmod {\,}}n\,}$

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

General idea

Let ${\displaystyle s=1/n}$ be the inverse of ${\displaystyle n}$ as a floating point number. Then

${\displaystyle a\,{\bmod {\,}}n=a-\lfloor as\rfloor n}$

where ${\displaystyle \lfloor x\rfloor }$ denotes the floor function. The result is exact, as long as ${\displaystyle s}$ 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 ${\displaystyle a\,{\bmod {\,}}n}$ using the method above, but with integers, the obvious analogue would be to use division by ${\displaystyle 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 ${\displaystyle 1/n}$ with a value ${\displaystyle m/2^{k}}$ because division by ${\displaystyle 2^{k}}$ is just a right-shift and so is cheap.

In order to calculate the best value for ${\displaystyle m}$ given ${\displaystyle 2^{k}}$ consider:

${\displaystyle {\frac {m}{2^{k}}}={\frac {1}{n}}\;\Longleftrightarrow \;m={\frac {2^{k}}{n}}}$

In order for ${\displaystyle m}$ to be an integer, we need to round ${\displaystyle {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 ${\displaystyle 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 ${\displaystyle [0,2n)}$ rather than ${\displaystyle [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 ${\displaystyle a}$ needs to be considered. The error of the approximation of ${\displaystyle 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 ${\displaystyle ae<1}$ then the reduction is valid thus ${\displaystyle a<1/e}$. The reduction function might not immediately give the wrong answer when ${\displaystyle a\geq 1/e}$ but the bounds on ${\displaystyle a}$ must be respected to ensure the correct answer in the general case.

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

Example

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

The smallest value of ${\displaystyle k}$ that makes sense is ${\displaystyle k=7}$ because if ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle k=9}$, we get ${\displaystyle m=512/101=5}$, which is a better approximation.

Now we consider the valid input ranges for ${\displaystyle k=7}$ and ${\displaystyle k=9}$. In the first case, ${\displaystyle e=1/n-m/2^{k}=1/101-1/128=27/12928}$ so ${\displaystyle a<1/e}$ implies ${\displaystyle a<478.81}$. Since ${\displaystyle 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 ${\displaystyle k=9}$ then ${\displaystyle e=1/101-5/512=7/51712}$ and so the maximum value of ${\displaystyle a}$ is 7387. (In practice the function happens to work until 7473.)

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

Proof for range for a specific k

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

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

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

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

The proof that ${\displaystyle 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 ${\displaystyle 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-{\frac {a}{2^{k}}}\cdot \left(2^{k}-(2^{k}\mod n)\right)+{\frac {n\cdot (ma\mod 2^{k})}{2^{k}}}<2n}$

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

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

${\displaystyle a-{\frac {nma}{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}$

${\displaystyle a-qn<2n}$

${\displaystyle 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. (1986). "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, A.; Govaerts, R.; Vandewalle, J. (1993). "Comparison of Three Modular Reduction Functions". In Stinson, Douglas R. (ed.). Advances in Cryptology — Crypto'93. Lecture Notes in Computer Science. 773. Springer. pp. 175–186. CiteSeerX 10.1.1.40.3779. ISBN 3540483292.
• Hasenplaugh, W.; Gaubatz, G.; Gopal, V. (2007). "Fast Modular Reduction" (PDF). 18th IEEE Symposium on Computer Arithmetic(ARITH'07). pp. 225–9. doi:10.1109/ARITH.2007.18. ISBN 0-7695-2854-6.