Английская Википедия:Barrett reduction
In modular arithmetic, Barrett reduction is a reduction algorithm introduced in 1986 by P.D. Barrett.[1]
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.
Historically, for values <math>a, b < n</math>, one computed <math>a b \, \bmod\, n \, </math> by applying Barrett reduction to the full product <math>a b </math>. Recently, it was shown that the full product is unnecessary if we can perform precomputation on one of the operands.[2][3]
General idea
We call a function <math>\left[ \, \right]: \mathbb{R} \to \mathbb{Z}</math> an integer approximation if <math>|\left[z\right] - z| \leq 1</math>. For a modulus <math>n</math> and an integer approximation <math>\left[\,\right]</math>, we define <math>\text{mod}^{\left[\,\right]} \, n: \mathbb{Z} \to (\mathbb{Z}/n\mathbb{Z}) </math> as
- <math> a \, \text{mod}^{\left[\,\right]} \, n = a - \left[a / n\right] n </math>.
Common choices of <math>\left[\,\right]</math> are floor, ceiling, and rounding functions.
Generally, Barrett multiplication starts by specifying two integer approximations <math>\left[\,\right]_0, \left[\,\right]_1</math> and computes a reasonably close approximation of <math>ab \, \bmod \, n</math> as
- <math> a b - \left[ \frac{a \, \left[ \frac{b R}{n} \right]_0 }{R} \right]_1 n</math>,
where <math>R</math> is a fixed constant, typically a power of 2, chosen so that multiplication and division by <math>R</math> can be performed efficiently.
The case <math>b = 1</math> was introduced by P.D. Barrett [1] for the floor-function case <math>\left[\,\right]_0 = \left[\,\right]_1 = \lfloor \, \rfloor</math>. The general case for <math>b</math> can be found in NTL.[2] The integer approximation view and the correspondence between Montgomery multiplication and Barrett multiplication was discovered by Hanno Becker, Vincent Hwang, Matthias J. Kannwischer, Bo-Yin Yang, and Shang-Yi Yang.[3]
Single-word Barrett reduction
Barrett initially considered an integer version of the above algorithm when the values fit into machine words. We illustrate the idea for the floor-function case with <math>b=1</math> and <math>R=2^k</math>.
When calculating <math>a \,\bmod\, n</math> for unsigned integers, the obvious analog would be to use division by <math>n</math>:
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, might not be a constant-time instruction on some CPUs, subjecting the operation to a timing attack. 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 it is cheap.
In order to calculate the best value for <math>m</math> given <math>2^k</math> consider:
- <math>\frac{m}{2^k} = \frac{1}{n} \;\Longleftrightarrow\; m = \frac{2^k}{n}</math>
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 used for unsigned arithmetic.
Thus we can approximate the function above with the following:
func reduce(a uint) uint {
q := (a * m) >> k // ">> k" denotes bitshift by k.
return a - q * n
}
However, since <math>m/2^k \le 1/n</math>, the value of q in that function can end up being one too small, and thus a 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:
func reduce(a uint) uint {
q := (a * m) >> k
a -= q * n
if a >= n {
a -= n
}
return a
}
Single-word Barrett multiplication
Suppose <math>b</math> is known. This allows us to precompute <math>\left\lfloor \frac{b R}{n} \right\rfloor</math> before we receive <math>a</math>. Barrett multiplication computes <math>a b</math>, approximates the high part of <math>a b</math> with <math> \left\lfloor \frac{a \left\lfloor \frac{b R}{n} \right\rfloor}{R} \right\rfloor \, n </math>, and subtracts the approximation. Since <math>\left\lfloor \frac{a \left\lfloor \frac{b R}{n} \right\rfloor}{R} \right\rfloor \, n</math> is a multiple of <math>n</math>, the resulting value <math>a b - \left\lfloor \frac{a \left\lfloor \frac{b R}{n} \right\rfloor}{R} \right\rfloor \, n</math> is a representative of <math>a b \, \bmod \, n</math>.
Correspondence between Barrett and Montgomery multiplications
Recall that unsigned Montgomery multiplication computes a representative of <math>a b \, \bmod \, n</math> as
- <math>
\frac{a \left(b R \, \bmod \, n \right) + \left( a \left( - b R \, \bmod \, n \right) n^{-1} \, \bmod \, R \right) n}{R} </math>.
In fact, this value is equal to <math>a b - \left\lfloor \frac{a \left\lfloor \frac{b R}{n} \right\rfloor}{R} \right\rfloor \, n</math>.
We prove the claim as follows.
- <math>
\begin{align} & & & a b - \left\lfloor \frac{a \left\lfloor \frac{b R}{n} \right\rfloor}{R} \right\rfloor \, n \\ & = & & a b - \frac{a \left\lfloor \frac{bR}{n} \right\rfloor - \left( a \left\lfloor \frac{bR}{n} \right\rfloor \, \bmod \, R \right) }{R} \, n \\ & = & & \left( \frac{a b R}{n} - a \left\lfloor \frac{bR}{n} \right\rfloor + \left( a \left\lfloor \frac{bR}{n} \right\rfloor \, \bmod \, R \right) \right) \frac{n}{R} \\ & = & & \left( \frac{a b R}{n} - a \frac{bR - \left(b R \, \bmod \, n \right)}{n} + \left( a \left\lfloor \frac{bR}{n} \right\rfloor \, \bmod \, R \right) \right) \frac{n}{R} \\ & = & & \left( \frac{a \left(b R \, \bmod \, n \right)}{n} + \left( a \left\lfloor \frac{bR}{n} \right\rfloor \, \bmod \, R \right) \right) \frac{n}{R} \\ & = & & \left( \frac{a \left(b R \, \bmod \, n \right)}{n} + \left( a \left( - b R \, \bmod \, n \right) n^{-1} \, \bmod \, R \right) \right) \frac{n}{R} \\ & = & & \frac{a \left(b R \, \bmod \, n \right) + \left( a \left( - b R \, \bmod \, n \right) n^{-1} \, \bmod \, R \right) n}{R}. \end{align} </math>
Generally, for integer approximations <math>\left[\,\right]_0, \left[\,\right]_1</math>, we have
- <math>
a b - \left[ \frac{a \, \left[ \frac{b R}{n} \right]_0 }{R} \right]_1 \, n = \frac{a \left( b R \, \text{mod}^{\left[\,\right]_0} \, n \right) + \left( a \left( - b R \, \text{mod}^{\left[\,\right]_0} \, q \right) n^{-1} \, \text{mod}^{\left[\,\right]_1} \, R \right) n}{R} </math>.[3]
Range of Barrett multiplication
We bound the output with <math> a b - \left\lfloor \frac{a \left\lfloor \frac{b R}{n} \right\rfloor}{R} \right\rfloor \, n = \frac{a \left(b R \, \bmod \, n \right) + \left( a \left( - b R \, \bmod \, n \right) n^{-1} \, \bmod \, R \right) n}{R} \leq \frac{a n + R n}{R} = n \left(1 + \frac{a}{R}\right) </math>.
Similar bounds hold for other kinds of integer approximation functions. For example, if we choose <math>\left[\,\right]_0 = \left[\,\right]_1 = \left\lfloor\,\right\rceil</math>, the rounding half up function, then we have
- <math>
\left| a b - \left\lfloor \frac{a \left\lfloor \frac{b R}{n} \right\rceil}{R} \right\rceil \, n \right| = \left| \frac{a \left(b R \, \text{mod}^{\pm} \, n \right) + \left( a \left( - b R \, \text{mod}^{\pm} \, n \right) n^{-1} \, \text{mod}^{\pm} \, R \right) n}{R} \right| \leq \left| \frac{a \frac{n}{2} + \frac{R}{2} n}{R} \right| = \frac{n}{2} \left(1 + \frac{|a|}{R} \right). </math>
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.[4]
Barrett algorithm for polynomials
It is also possible to use Barrett algorithm for polynomial division, by reversing polynomials and using X-adic arithmetic.[5]
See also
- Montgomery reduction is another similar algorithm.
References
Sources
