Barrett reduction

In modular arithmetic, Barrett reduction is a reduction algorithm introduced in 1986 by P.D. Barrett.

A naive way of computing

[math]\displaystyle{ 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]\displaystyle{ n }[/math] is constant, and [math]\displaystyle{ a\lt n^2 }[/math], replacing divisions by multiplications.

Historically, for values [math]\displaystyle{ a, b \lt n }[/math], one computed [math]\displaystyle{ a b \, \bmod\, n \, }[/math] by applying Barrett reduction to the full product [math]\displaystyle{ a b }[/math]. Recently, it was shown that the full product is unnecessary if we can perform precomputation on one of the operands.

General idea

We call a function [math]\displaystyle{ \left[ \, \right]: \mathbb{R} \to \mathbb{Z} }[/math] an integer approximation if [math]\displaystyle{ |\left[z\right] - z| \leq 1 }[/math]. For a modulus [math]\displaystyle{ n }[/math] and an integer approximation [math]\displaystyle{ \left[\,\right] }[/math], we define [math]\displaystyle{ \text{mod}^{\left[\,\right]} \, n: \mathbb{Z} \to (\mathbb{Z}/n\mathbb{Z}) }[/math] as

[math]\displaystyle{ a \, \text{mod}^{\left[\,\right]} \, n = a - \left[a / n\right] n }[/math].

Common choices of [math]\displaystyle{ \left[\,\right] }[/math] are floor, ceiling, and rounding functions.

Generally, Barrett multiplication starts by specifying two integer approximations [math]\displaystyle{ \left[\,\right]_0, \left[\,\right]_1 }[/math] and computes a reasonably close approximation of [math]\displaystyle{ ab \, \bmod \, n }[/math] as

[math]\displaystyle{ a b - \left[ \frac{a \, \left[ \frac{b R}{n} \right]_0 }{R} \right]_1 n }[/math],

where [math]\displaystyle{ R }[/math] is a fixed constant, typically a power of 2, chosen so that multiplication and division by [math]\displaystyle{ R }[/math] can be performed efficiently.

The case [math]\displaystyle{ b = 1 }[/math] was introduced by P.D. Barrett for the floor-function case [math]\displaystyle{ \left[\,\right]_0 = \left[\,\right]_1 = \lfloor \, \rfloor }[/math]. The general case for [math]\displaystyle{ b }[/math] can be found in NTL. 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.

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]\displaystyle{ b=1 }[/math] and [math]\displaystyle{ R=2^k }[/math].

When calculating [math]\displaystyle{ a \,\bmod\, n }[/math] for unsigned integers, the obvious analog would be to use division by [math]\displaystyle{ 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]\displaystyle{ 1/n }[/math] with a value [math]\displaystyle{ m/2^k }[/math] because division by [math]\displaystyle{ 2^k }[/math] is just a right-shift, and so it is cheap.

In order to calculate the best value for [math]\displaystyle{ m }[/math] given [math]\displaystyle{ 2^k }[/math] consider:

[math]\displaystyle{ \frac{m}{2^k} = \frac{1}{n} \;\Longleftrightarrow\; m = \frac{2^k}{n} }[/math]

For [math]\displaystyle{ m }[/math] to be an integer, we need to round [math]\displaystyle{ {2^k}/{n} }[/math] somehow. Rounding to the nearest integer will give the best approximation but can result in [math]\displaystyle{ m/2^k }[/math] being larger than [math]\displaystyle{ 1/n }[/math], which can cause underflows. Thus [math]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ [0, 2n) }[/math] rather than [math]\displaystyle{ [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]\displaystyle{ b }[/math] is known. This allows us to precompute [math]\displaystyle{ \left\lfloor \frac{b R}{n} \right\rfloor }[/math] before we receive [math]\displaystyle{ a }[/math]. Barrett multiplication computes [math]\displaystyle{ a b }[/math], approximates the high part of [math]\displaystyle{ a b }[/math] with [math]\displaystyle{ \left\lfloor \frac{a \left\lfloor \frac{b R}{n} \right\rfloor}{R} \right\rfloor \, n }[/math], and subtracts the approximation. Since [math]\displaystyle{ \left\lfloor \frac{a \left\lfloor \frac{b R}{n} \right\rfloor}{R} \right\rfloor \, n }[/math] is a multiple of [math]\displaystyle{ n }[/math], the resulting value [math]\displaystyle{ a b - \left\lfloor \frac{a \left\lfloor \frac{b R}{n} \right\rfloor}{R} \right\rfloor \, n }[/math] is a representative of [math]\displaystyle{ a b \, \bmod \, n }[/math].

Correspondence between Barrett and Montgomery multiplications

Recall that unsigned Montgomery multiplication computes a representative of [math]\displaystyle{ a b \, \bmod \, n }[/math] as

[math]\displaystyle{ \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]\displaystyle{ 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]\displaystyle{ \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]\displaystyle{ \left[\,\right]_0, \left[\,\right]_1 }[/math], we have

[math]\displaystyle{ 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].

Range of Barrett multiplication

We bound the output with [math]\displaystyle{ 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]\displaystyle{ \left[\,\right]_0 = \left[\,\right]_1 = \left\lfloor\,\right\rceil }[/math], the rounding half up function, then we have

[math]\displaystyle{ \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.

Barrett algorithm for polynomials

It is also possible to use Barrett algorithm for polynomial division, by reversing polynomials and using X-adic arithmetic.

See also

• Montgomery reduction is another similar algorithm.

Sources

• Bosselaers, A.; Govaerts, R.; Vandewalle, J. (1993). "Comparison of Three Modular Reduction Functions". in Stinson, Douglas R.. Advances in Cryptology – Crypto'93. Lecture Notes in Computer Science. 773. Springer. pp. 175–186. ISBN 3540483292. https://books.google.com/books?id=sqqoCAAAQBAJ&pg=PA175. 
• Hasenplaugh, W.; Gaubatz, G.; Gopal, V. (2007). "Fast Modular Reduction". 18th IEEE Symposium on Computer Arithmetic(ARITH'07). pp. 225–229. doi:10.1109/ARITH.2007.18. ISBN 978-0-7695-2854-0. http://www.acsel-lab.com/arithmetic/arith18/papers/ARITH18_Hasenplaugh.pdf.