# 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\,{\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 , replacing divisions by multiplications.

## General idea

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

$a\,{\bmod {\,}}n=a-\lfloor as\rfloor n$ where $\lfloor x\rfloor$ denotes the floor function. The result is exact, as long as $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 $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 $m/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:

${\frac {m}{2^{k}}}={\frac {1}{n}}\;\Longleftrightarrow \;m={\frac {2^{k}}{n}}$ 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 $m/2^{k}$ being larger than $1/n$ , which can cause underflows. Thus $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 $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 $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:

$e={\frac {1}{n}}-{\frac {m}{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\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 $k=7$ because if $2^{k} then the reduction will only be valid for values that are already minimal! For a value of seven, $m=\lfloor 2^{k}/n\rfloor =\lfloor 128/101\rfloor =1$ . For a value of eight $m=\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=9$ , we get $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-m/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\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 $2^{k_{0}}>n$ . Take $k_{0}+1$ as a reasonable value for $k$ in the above equations. As in the code snippets above, let

• $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 $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 The proof that $r<2n$ follows:

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

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

${\frac {a\cdot (2^{k}\mod n)}{2^{k}}}+n\cdot {\frac {ma\mod 2^{k}}{2^{k}}}<2n$ $a-\left(a-{\frac {a\cdot (2^{k}\mod n)}{2^{k}}}\right)+{\frac {n\cdot (ma\mod 2^{k})}{2^{k}}}<2n$ $a-{\frac {a}{2^{k}}}\cdot \left(2^{k}-(2^{k}\mod n)\right)+{\frac {n\cdot (ma\mod 2^{k})}{2^{k}}}<2n$ $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$ $a-{\frac {na}{2^{k}}}\cdot \left\lfloor {\frac {2^{k}}{n}}\right\rfloor \ +{\frac {n\cdot (ma\mod 2^{k})}{2^{k}}}<2n$ $a-{\frac {nma}{2^{k}}}+{\frac {n\cdot (ma\mod 2^{k})}{2^{k}}}<2n$ $a-\left({\frac {ma-(ma\mod 2^{k})}{2^{k}}}\right)\cdot n<2n$ $a-\left\lfloor {\frac {ma}{2^{k}}}\right\rfloor \cdot n<2n$ $a-qn<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.