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<n^{2}$, 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 {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}\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}<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 (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2/256} ) is exactly the same as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/128} . For Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k = 9} , we get Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m = 512 / 101 = 5} , which is a better approximation.

Now we consider the valid input ranges for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k = 7} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k = 9} . In the first case, $e=1/n-m/2^{k}=1/101-1/128=27/12928$ so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a < 1/e} implies Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a < 478.81} . Since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k = 9} then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e = 1/101 - 5/512 = 7/51712} and so the maximum value of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 81/8192} . However, note that the intermediate value Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle ax} in the calculation will then overflow an unsigned 16-bit value when Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 810 \le a} , thus Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k = 7} works better in this situation.

Proof for range for a specific k

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k_0} be the smallest integer such that $2^{k_{0}}>n$. Take Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k_0+1} as a reasonable value for $k$ in the above equations. As in the code snippets above, let

• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q = \left\lfloor \frac{m a}{2^k} \right\rfloor } and
• $r=a-qn$.

Because of the floor function, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} is an integer and $r\equiv a{\pmod {n}}$. Also, if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a < 2 ^ k} then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r < 2n} . In that case, writing the snippets above as an expression:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \,\bmod\, n = \begin{cases} r & \text{if } r<n \\ r-n & \text{otherwise} \end{cases}}

The proof that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r < 2n} follows:

If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a < 2 ^ k} , then

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{a}{2 ^ k} \cdot (2 ^ k \mod n) < n}

Since $n\cdot {\frac {ma\mod 2^{k}}{2^{k}}}<n$ regardless of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} , it follows that

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{a\cdot (2 ^ k \mod n)}{2 ^ k} + n\cdot\frac{m a \mod 2^k}{2^k} < 2n}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a - \left(a - \frac{a\cdot (2 ^ k \mod n)}{2 ^ k}\right) + \frac{(n \cdot (m a \mod 2^k))}{2^k} < 2n}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a - \frac{m n a}{2 ^ k} + \frac{(n \cdot (m a \mod 2^k))}{2^k} < 2n}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a - \left(\frac{m a - (m a \mod 2^k)}{2^k}\right)\cdot n < 2n}

$a-\left\lfloor {\frac {ma}{2^{k}}}\right\rfloor \cdot n<2n$

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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.

See also

Montgomery reduction is another similar algorithm.

Source

http://wikipedia.org/