Barrett reduction - Revision history

Admin: Created page with "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. \,$
2019-03-20T04:29:02Z

Created page with "In modular arithmetic, '''Barrett reduction''' is a reduction algorithm introduced in 1986 by P.D. Barrett. A naive way of computing :<math>c = a \,\bmod\, n. \, </ma..."

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

:<math>c = a \,\bmod\, n. \, </math>

would be to use a fast [[division algorithm]]. Barrett reduction is an algorithm designed to optimize this operation assuming <math>n</math> is constant, and <math>a<n^2</math>, replacing divisions by multiplications.

== General idea ==

Let <math>s=1/n</math> be the inverse of <math>n</math> as a [[floating point]] number. Then

:<math>a \,\bmod\, n = a-\lfloor a s\rfloor n </math>

where <math>\lfloor x \rfloor</math> denotes the [[floor function]]. The result is exact, as long as <math>s</math> 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 <math>a \,\bmod\, n</math> using the method above, but with integers, the obvious analogue would be to use division by <math>n</math>:

<syntaxhighlight lang="go">
func reduce(a uint) uint {
q := a / n // Division implicitly returns the floor of the result.
return a - q * n
}
</syntaxhighlight>

However, division can be expensive and, in cryptographic settings, may not be a constant-time instruction on some CPUs. Thus Barrett reduction approximates <math>1/n</math> with a value <math>m/2^k</math> because division by <math>2^k</math> is just a right-shift and so is cheap.

In order to calculate the best value for <math>m</math> given <math>2^k</math> consider:

:<math>\frac{1}{n} = \frac{n(\frac{2^k}{n})} = \frac{2^k} = \frac{m}{2^k}</math>

In order for <math>m</math> to be an integer, we need to round <math>{2^k}/{n}</math> somehow. Rounding to the nearest integer will give the best approximation but can result in <math>m/2^k</math> being larger than <math>1/n</math>, which can cause underflows. Thus <math>m = \lfloor {2^k}/{n} \rfloor</math> is generally used.

Thus we can approximate the function above with:

<syntaxhighlight lang="go">
func reduce(a uint) uint {
q := (a * m) >> k // ">> k" denotes bitshift by k.
return a - q * n
}
</syntaxhighlight>

However, since <math>m/2^k \le 1/n</math>, the value of <code>q</code> in that function can end up being one too small, and thus <code>a</code> is only guaranteed to be within <math>[0, 2n)</math> rather than <math>[0, n)</math> as is generally required. A conditional subtraction will correct this:

<syntaxhighlight lang="go">
func reduce(a uint) uint {
q := (a * m) >> k
a -= q * n
if n <= a {
a -= n
}
return a
}
</syntaxhighlight>

Since <math>m/2^k</math> is only an approximation, the valid range of <math>a</math> needs to be considered. The error of the approximation of <math>1/n</math> is:

:<math>e = \frac{1}{n} - \frac{m}{2^k}</math>

Thus the error in the value of <code>q</code> is <math>ae</math>. As long as <math>ae < 1</math> then the reduction is valid thus <math>a < 1/e</math>. The reduction function might not immediately give the wrong answer when <math>a \ge 1/e</math> but the bounds on <math>a</math> must be respected to ensure the correct answer in the general case.

By choosing larger values of <math>k</math>, the range of values of <math>a</math> for which the reduction is valid can be increased, but larger values of <math>k</math> may cause overflow problems elsewhere.

=== Example ===

Consider the case of <math>n = 101</math> when operating with 16-bit integers.

The smallest value of <math>k</math> that makes sense is <math>k = 7</math> because if <math>2^k < n</math> then the reduction will only be valid for values that are already minimal! For a value of seven, <math>m = \lfloor 2^k / n \rfloor = \lfloor 128 / 101 \rfloor = 1</math>. For a value of eight <math>m = \lfloor 256 / 101 \rfloor = 2</math>. Thus <math>k = 8</math> provides no advantage because the approximation of <math>1/101</math> in that case (<math>2/256</math>) is exactly the same as <math>1/128</math>. For <math>k = 9</math>, we get <math>m = 512 / 101 = 5</math>, which is a better approximation.

Now we consider the valid input ranges for <math>k = 7</math> and <math>k = 9</math>. In the first case, <math>e = 1/n - m/2^k = 1/101 - 1/128 = 27/12928</math> so <math>a < 1/e</math> implies <math>a < 478.81</math>. Since <math>a</math> is an integer, effectively the maximum value is 478. (In practice the function happens to work for values up to 504.)

If we take <math>k = 9</math> then <math>e = 1/101 - 5/512 = 7/51712</math> and so the maximum value of <math>a</math> is 7387. (In practice the function happens to work until 7473.)

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

=== Proof for range for a specific k ===

Let <math>k_0</math> be the smallest integer such that <math>2^{k_0}>n</math>. Take <math>k_0+1</math> as a reasonable value for <math>k</math> in the above equations. As in the code snippets above, let

* <math>q = \left\lfloor \frac{m a}{2^k} \right\rfloor </math> and
* <math>r = a - q n</math>.

Because of the [[floor function]], <math>q</math> is an integer and <math>r \equiv a \pmod{n}</math>. Also, if <math>a < 2 ^ k</math> then <math>r < 2n</math>. In that case, writing the snippets above as an expression:
:<math>a \,\bmod\, n = \begin{cases} r & \text{if } r<n \\ r-n & \text{otherwise} \end{cases}</math>

The proof that <math>r < 2n</math> follows:

If <math>a < 2 ^ k</math>, then
:<math>\frac{a}{2 ^ k} \cdot (2 ^ k \mod n) < n</math>

Since <math>n\cdot\frac{m a \mod 2^k}{2^k} < n</math> regardless of <math>a</math>, it follows that
:<math> \frac{a\cdot (2 ^ k \mod n)}{2 ^ k} + n\cdot\frac{m a \mod 2^k}{2^k} < 2n</math>
:<math> a - \left(a - \frac{a\cdot (2 ^ k \mod n)}{2 ^ k}\right) + \frac{(n \cdot (m a \mod 2^k))}{2^k} < 2n</math>
:<math> a - \left(\left\lfloor\frac{2 ^ k}{n}\right\rfloor \cdot \frac{n a}{2 ^ k}\right) + \frac{(n \cdot (m a \mod 2^k))}{2^k} < 2n</math>
:<math> a - \frac{m n a}{2 ^ k} + \frac{(n \cdot (m a \mod 2^k))}{2^k} < 2n</math>
:<math> a - \left(\frac{m a - (m a \mod 2^k)}{2^k}\right)\cdot n < 2n</math>
:<math> a - \left\lfloor\frac{m a}{2 ^ k}\right\rfloor\cdot n < 2n</math>
:<math>r < 2n</math>

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

== See also ==

[[Montgomery reduction]] is another similar algorithm.

==Source==

[http://wikipedia.org/ http://wikipedia.org/]

[[Category:Cryptography]]
[[Category:Cryptographic algorithms]]