Barrett reduction

In , 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 . Barrett reduction is an algorithm designed to optimize this operation assuming $n$ is constant, and $a<n^2$ , replacing divisions by multiplications.

1 General idea
2 Single-word Barrett reduction
- 2.1 Example
- 2.2 Proof for range for a specific k
3 Multi-word Barrett reduction
4 See also
5 Source

General idea

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

a ,bmod, n = a-lfloor a srfloor n

where $lfloor x rfloor$ denotes the . 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{1}{n} = frac{n(frac{2^k}{n})} = frac{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 $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 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 * 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 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 = 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 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^{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 = leftlfloor frac{m a}{2^k} rightrfloor$ and
$r = a - q n$ .

Because of the , $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<n \ r-n & text{otherwise} end{cases}

The proof that $r < 2n$ follows:

If $a < 2 ^ k$ , then

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

Since $ncdotfrac{m a mod 2^k}{2^k} < n$ regardless of $a$ , it follows that

frac{acdot (2 ^ k mod n)}{2 ^ k} + ncdotfrac{m a mod 2^k}{2^k} < 2n

a - left(a - frac{acdot (2 ^ k mod n)}{2 ^ k}right) + frac{(n cdot (m a mod 2^k))}{2^k} < 2n

a - left(leftlfloorfrac{2 ^ k}{n}rightrfloor cdot frac{n a}{2 ^ k}right) + frac{(n cdot (m a mod 2^k))}{2^k} < 2n

a - frac{m n a}{2 ^ k} + frac{(n cdot (m a mod 2^k))}{2^k} < 2n

a - left(frac{m a - (m a mod 2^k)}{2^k}right)cdot n < 2n

a - leftlfloorfrac{m a}{2 ^ k}rightrfloorcdot n < 2n

r < 2n

Multi-word Barrett reduction

Barrett’s primary motivation for considering reduction was the implementation of , 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.

Source

http://wikipedia.org/

Categories: