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 a s\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

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 it is cheap.

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

:$\frac = \frac \;\Longleftrightarrow\; m = \frac$

In order for $m$ to be an integer, we need to round $/$ 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 / \rfloor$ is generally used.

Thus we can approximate the function above with:

func reduce(a uint) uint

However, since $m/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 $$
func reduce(a uint) uint

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 - \frac$

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 $k = 7$ because if $2^k < n$ 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 = \lfloor 512 / 101 \rfloor = 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 \le 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^>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 \right\rfloor$ and
* $r = a - q n$.

Because of the floor function, $q$ is an integer and $r \equiv a \pmod$. Also, if $a \le 2 ^ k$ then $r < 2n$. In that case, writing the snippets above as an expression:
:a \,\bmod\, n = \begin r & \text r

The proof that $r < 2n$ follows:

If $a \le 2 ^ k$, then
:$\frac \cdot (2 ^ k \mod n) < n$

Since $n\cdot\frac < n$ regardless of $a$, it follows that
:$\frac + n\cdot\frac < 2n$
:$a - \left(a - \frac\right) + \frac < 2n$
:$a - \frac \cdot \left(2^k - (2^k \mod n)\right) + \frac < 2n$
:$a - \frac \cdot \left(\frac\right) + \frac < 2n$
:$a - \frac \cdot \left\lfloor\frac\right\rfloor\ + \frac < 2n$
:$a - \frac + \frac < 2n$
:$a - \left(\frac\right)\cdot n < 2n$
:$a - \left\lfloor\frac\right\rfloor\cdot n < 2n$
:$a - q n < 2n$
:$r < 2n$

Multi-word Barrett reduction

Barrett's primary motivation for considering reduction was the implementation of RSA (cryptosystem)">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''.

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.

References

Sources

*
*
{{refend

Computer arithmetic
Modular arithmetic