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:

{\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 $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 seven 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$ equal to nine, $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 $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<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 $n\cdot {\frac {ma\mod 2^{k}}{2^{k}}}<n$ 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-\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

a-{\frac {mna}{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

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]

References

↑ 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.
↑ 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

This article is issued from Wikipedia - version of the 10/27/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.