Barrett reduction

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

A naive way of computing

${\displaystyle c=a\,{\bmod {\,}}n\,}$

would be to use a fast division algorithm. Barrett reduction is an algorithm designed to optimize this operation assuming ${\displaystyle n}$ is constant, and ${\displaystyle a<n^{2}}$, replacing divisions by multiplications.

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

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

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

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

Generally, Barrett multiplication starts by specifying two integer approximations ${\displaystyle \left[\,\right]_{0},\left[\,\right]_{1}}$ and computes a reasonably close approximation of ${\displaystyle ab\,{\bmod {\,}}n}$ as

${\displaystyle ab-\left[{\frac {a\,\left[{\frac {bR}{n}}\right]_{0}}{R}}\right]_{1}n}$,

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

The case ${\displaystyle b=1}$ was introduced by P.D. Barrett ^[1] for the floor-function case ${\displaystyle \left[\,\right]_{0}=\left[\,\right]_{1}=\lfloor \,\rfloor }$. The general case for ${\displaystyle b}$ 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]

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

When calculating ${\displaystyle a\,{\bmod {\,}}n}$ for unsigned integers, the obvious analog would be to use division by ${\displaystyle 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, might not be a constant-time instruction on some CPUs, subjecting the operation to a timing attack. Thus Barrett reduction approximates ${\displaystyle 1/n}$ with a value ${\displaystyle m/2^{k}}$ because division by ${\displaystyle 2^{k}}$ is just a right-shift, and so it is cheap.

In order to calculate the best value for ${\displaystyle m}$ given ${\displaystyle 2^{k}}$ consider:

${\displaystyle {\frac {m}{2^{k}}}={\frac {1}{n}}\;\Longleftrightarrow \;m={\frac {2^{k}}{n}}}$

For ${\displaystyle m}$ to be an integer, we need to round ${\displaystyle {2^{k}}/{n}}$ somehow. Rounding to the nearest integer will give the best approximation but can result in ${\displaystyle m/2^{k}}$ being larger than ${\displaystyle 1/n}$, which can cause underflows. Thus ${\displaystyle m=\lfloor {2^{k}}/{n}\rfloor }$ 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 ${\displaystyle 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 ${\displaystyle [0,2n)}$ rather than ${\displaystyle [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 a >= n {
        a -= n
    }
    return a
}

Suppose ${\displaystyle b}$ is known. This allows us to precompute ${\displaystyle \left\lfloor {\frac {bR}{n}}\right\rfloor }$ before we receive ${\displaystyle a}$. Barrett multiplication computes ${\displaystyle ab}$, approximates the high part of ${\displaystyle ab}$ with ${\displaystyle \left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n}$, and subtracts the approximation. Since ${\displaystyle \left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n}$ is a multiple of ${\displaystyle n}$, the resulting value ${\displaystyle ab-\left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n}$ is a representative of ${\displaystyle ab\,{\bmod {\,}}n}$.

Recall that unsigned Montgomery multiplication computes a representative of ${\displaystyle ab\,{\bmod {\,}}n}$ as

${\displaystyle {\frac {a\left(bR\,{\bmod {\,}}n\right)+\left(a\left(-bR\,{\bmod {\,}}n\right)n^{-1}\,{\bmod {\,}}R\right)n}{R}}}$.

In fact, this value is equal to ${\displaystyle ab-\left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n}$.

We prove the claim as follows.

${\displaystyle {\begin{aligned}&&&ab-\left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n\\&=&&ab-{\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 {abR}{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 {abR}{n}}-a{\frac {bR-\left(bR\,{\bmod {\,}}n\right)}{n}}+\left(a\left\lfloor {\frac {bR}{n}}\right\rfloor \,{\bmod {\,}}R\right)\right){\frac {n}{R}}\\&=&&\left({\frac {a\left(bR\,{\bmod {\,}}n\right)}{n}}+\left(a\left\lfloor {\frac {bR}{n}}\right\rfloor \,{\bmod {\,}}R\right)\right){\frac {n}{R}}\\&=&&\left({\frac {a\left(bR\,{\bmod {\,}}n\right)}{n}}+\left(a\left(-bR\,{\bmod {\,}}n\right)n^{-1}\,{\bmod {\,}}R\right)\right){\frac {n}{R}}\\&=&&{\frac {a\left(bR\,{\bmod {\,}}n\right)+\left(a\left(-bR\,{\bmod {\,}}n\right)n^{-1}\,{\bmod {\,}}R\right)n}{R}}.\end{aligned}}}$

Generally, for integer approximations ${\displaystyle \left[\,\right]_{0},\left[\,\right]_{1}}$, we have

${\displaystyle ab-\left[{\frac {a\,\left[{\frac {bR}{n}}\right]_{0}}{R}}\right]_{1}\,n={\frac {a\left(bR\,{\text{mod}}^{\left[\,\right]_{0}}\,n\right)+\left(a\left(-bR\,{\text{mod}}^{\left[\,\right]_{0}}\,q\right)n^{-1}\,{\text{mod}}^{\left[\,\right]_{1}}\,R\right)n}{R}}}$.^[3]

We bound the output with ${\displaystyle ab-\left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n={\frac {a\left(bR\,{\bmod {\,}}n\right)+\left(a\left(-bR\,{\bmod {\,}}n\right)n^{-1}\,{\bmod {\,}}R\right)n}{R}}\leq {\frac {an+Rn}{R}}=n\left(1+{\frac {a}{R}}\right)}$.

Similar bounds hold for other kinds of integer approximation functions. For example, if we choose ${\displaystyle \left[\,\right]_{0}=\left[\,\right]_{1}=\left\lfloor \,\right\rceil }$, the rounding half up function, then we have

${\displaystyle \left|ab-\left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rceil }{R}}\right\rceil \,n\right|=\left|{\frac {a\left(bR\,{\text{mod}}^{\pm }\,n\right)+\left(a\left(-bR\,{\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).}$

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]

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

• Montgomery reduction is another similar algorithm.