# Barrett reduction

In modular arithmetic, Barrett reduction is an algorithm designed to optimize the calculation of $a\,{\bmod {\,}}n\,$ without needing a fast division algorithm. It replaces divisions with multiplications, and can be used when $n$ is constant and $a<n^{2}$. It was introduced in 1986 by P.D. Barrett.
Historically, for values $a,b<n$, one computed $ab\,{\bmod {\,}}n\,$ by applying Barrett reduction to the full product $ab$. In 2021, Becker et al. showed that the full product is unnecessary if we can perform precomputation on one of the operands.

## General idea

We call a function $\left[\,\right]:\mathbb {R} \to \mathbb {Z}$ an integer approximation if $|\left[z\right]-z|\leq 1$. For a modulus $n$ and an integer approximation $\left[\,\right]$, we define ${\text{mod}}^{\left[\,\right]}\,n:\mathbb {Z} \to (\mathbb {Z} /n\mathbb {Z} )$ as
    $a\,{\text{mod}}^{\left[\,\right]}\,n=a-\left[a/n\right]n$.
Common choices of $\left[\,\right]$ are floor, ceiling, and rounding functions.
Generally, Barrett multiplication starts by specifying two integer approximations $\left[\,\right]_{0},\left[\,\right]_{1}$ and computes a reasonably close approximation of $ab\,{\bmod {\,}}n$ as
    $ab-\left[{\frac {a\,\left[{\frac {bR}{n}}\right]_{0}}{R}}\right]_{1}n$,
where $R$ is a fixed constant, typically a power of 2, chosen so that multiplication and division by $R$ can be performed efficiently.
The case $b=1$ was introduced by P.D. Barrett for the floor-function case $\left[\,\right]_{0}=\left[\,\right]_{1}=\lfloor \,\rfloor$. The general case for $b$ 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 $b=1$ and $R=2^{k}$.
When calculating $a\,{\bmod {\,}}n$ for unsigned integers, the obvious analog would be to use division by $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 $1/n$ with a value $m/2^{k}$ because division by $2^{k}$ is just a right-shift, and so it is cheap.
In order to calculate the best value for $m$ given $2^{k}$ consider:
    ${\frac {m}{2^{k}}}={\frac {1}{n}}\;\Longleftrightarrow \;m={\frac {2^{k}}{n}}$
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 used for unsigned arithmetic.
Thus we can approximate the function above with the following:
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:

## Single-word Barrett multiplication

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

## Correspondence between Barrett and Montgomery multiplications

Recall that unsigned Montgomery multiplication computes a representative of $ab\,{\bmod {\,}}n$ as
    ${\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 $ab-\left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n$.
We prove the claim as follows.
    ${\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 $\left[\,\right]_{0},\left[\,\right]_{1}$, we have
    $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}}$.

## Range of Barrett multiplication

We bound the output with $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 $\left[\,\right]_{0}=\left[\,\right]_{1}=\left\lfloor \,\right\rceil$, the rounding half up function, then we have
    $\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 {\frac {|a|{\frac {n}{2}}+{\frac {R}{2}}n}{R}}={\frac {n}{2}}\left(1+{\frac {|a|}{R}}\right).$
It is common to select R such that ${\frac {a}{R}}<1$ (or ${\frac {\left|a\right|}{R}}<1$ in the $\left[\,\right]_{0}=\left[\,\right]_{1}=\left\lfloor \,\right\rceil$ case) so that the output remains within $0$ and $2n$ ($-n$ and $n$ resp.), and therefore only one check is performed to obtain the final result between $0$ and $n$. Furthermore, one can skip the check and perform it once at the end of an algorithm at the expense of larger inputs to the field arithmetic operations.

## Barrett multiplication non-constant operands

The Barrett multiplication previously described requires a constant operand b to pre-compute $\left[{\frac {bR}{n}}\right]_{0}$ ahead of time. Otherwise, the operation is not efficient. It is common to use Montgomery multiplication when both operands are non-constant as it has better performance. However, Montgomery multiplication requires a conversion to and from Montgomery domain which means it is expensive when a few modular multiplications are needed.
To perform Barrett multiplication with non-constant operands, one can set $a$ as the product of the operands and set $b$ to $1$. This leads to
$a-\left[{\frac {a\,\left[{\frac {R}{n}}\right]_{0}}{R}}\right]_{1}\,n={\frac {a\left(R\,{\text{mod}}^{\left[\,\right]_{0}}\,n\right)+\left(a\left(-R\,{\text{mod}}^{\left[\,\right]_{0}}\,q\right)n^{-1}\,{\text{mod}}^{\left[\,\right]_{1}}\,R\right)n}{R}}$
A quick check on the bounds yield the following in $\left[\,\right]_{0}=\left[\,\right]_{1}=\left\lfloor \,\right\rfloor$ case
${\begin{aligned}a-\left\lfloor {\frac {a\,\left\lfloor {\frac {R}{n}}\right\rfloor }{R}}\right\rfloor \,n&={\frac {a\left(R\,{\bmod {\,}}n\right)+\left(a\left(-R\,{\bmod {\,}}n\right)n^{-1}\,{\bmod {\,}}R\right)n}{R}}\\&\leq {\frac {a(R\,{\bmod {\,}}n)+Rn}{R}}=n\left(1+{\frac {a(R\,{\bmod {\,}}n)}{Rn}}\right)\end{aligned}}$
and the following in $\left[\,\right]_{0}=\left[\,\right]_{1}=\left\lfloor \,\right\rceil$ case
${\begin{aligned}\left|a-\left\lfloor {\frac {a\left\lfloor {\frac {R}{n}}\right\rceil }{R}}\right\rceil \,n\right|&=\left|{\frac {a\left(R\,{\text{mod}}^{\pm }\,n\right)+\left(a\left(-R\,{\text{mod}}^{\pm }\,n\right)n^{-1}\,{\text{mod}}^{\pm }\,R\right)n}{R}}\right|\\&\leq {\frac {|a(R\,{\text{mod}}^{\pm }\,n)|+{\frac {R}{2}}n}{R}}={\frac {n}{2}}\left(1+{\frac {|a(R\,{\text{mod}}^{\pm }\,n)|}{Rn}}\right)\end{aligned}}$
Setting $R>|a|$ will always yield one check on the output. However, a tighter constraint on $R$ might be possible since $R\,{\text{mod}}^{\left[\,\right]_{0}}\,n$ is a constant that is sometimes significantly smaller than $n$.
A small issue arises with performing the following product $a\,\left[{\frac {R}{n}}\right]_{0}$ since $a$ is already a product of two operands. Assuming $n$ fits in $w$ bits, then $a$ would fit in $2w$ bits and $\left[{\frac {R}{n}}\right]_{0}$ would fit in $w$ bits. Their product would require a $2w\times w$ multiplication which might require fragmenting in systems that cannot perform the product in one operation.
An alternative approach is to perform the following Barrett reduction:
$a-\left[{\frac {\left[{\frac {a}{R_{0}}}\right]_{2}\,\left[{\frac {R}{n}}\right]_{0}}{R_{1}}}\right]_{1}\,n={\frac {a\left(R\,{\text{mod}}^{\left[\,\right]_{0}}\,n\right)+\left(a\,{\text{mod}}^{\left[\,\right]_{2}}\,R_{0}\right)\left(R-R\,{\text{mod}}^{\left[\,\right]_{0}}\,n\right)+\left(\left[{\frac {a}{R_{0}}}\right]_{2}\,\left[{\frac {R}{n}}\right]_{0}\,{\text{mod}}^{\left[\,\right]_{1}}\,R_{1}\right)R_{0}n}{R}}$
where $R_{0}=2^{k-\beta }$, $R1=2^{\alpha +\beta }$, $R=R_{0}\cdot R_{1}=2^{k+\alpha }$, and $k$ is the bit-length of $n$.
Bound check in the case $\left[\,\right]_{0}=\left[\,\right]_{1}=\left[\,\right]_{2}=\left\lfloor \,\right\rfloor$ yields the following
${\begin{aligned}a-\left\lfloor {\frac {\left\lfloor {\frac {a}{R_{0}}}\right\rfloor \,\left\lfloor {\frac {R}{n}}\right\rfloor }{R}}\right\rfloor \,n&\leq {\frac {a\left(R\,{\bmod {\,}}n\right)+R_{0}R-R_{0}\left(R\,{\bmod {\,}}n\right)+Rn}{R}}\\&=n\left(1+{\frac {a(R\,{\bmod {\,}}n)}{Rn}}+{\frac {R_{0}}{n}}-{\frac {R\,{\bmod {\,}}n}{R_{1}n}}\right)\end{aligned}}$
and for the case $\left[\,\right]_{0}=\left[\,\right]_{1}=\left[\,\right]_{2}=\left\lfloor \,\right\rceil$ yields the following
${\begin{aligned}\left|a-\left\lfloor {\frac {\left\lfloor {\frac {a}{R_{0}}}\right\rceil \left\lfloor {\frac {R}{n}}\right\rceil }{R}}\right\rceil \,n\right|&\leq {\frac {|a\left(R\,{\text{mod}}^{\pm }\,n\right)|+R_{0}R/2+R_{0}|(R\,{\text{mod}}^{\pm }\,n)|/2+Rn/2}{R}}\\&={\frac {n}{2}}\left(1+{\frac {2|a(R\,{\text{mod}}^{\pm }\,n)|}{Rn}}+{\frac {R_{0}}{n}}+{\frac {|R\,{\text{mod}}^{\pm }\,n|}{R_{1}n}}\right)\end{aligned}}$
For any modulus and assuming $|a|<2^{k+\gamma }$, the bound inside the parenthesis in both cases is less than or equal:
$1+{\frac {(2^{k+\gamma })(n)}{(2^{k+\alpha })(n)}}+{\frac {2^{k-\beta }}{n}}+\epsilon \leq 1+{\frac {2^{k+\gamma }}{2^{k+\alpha }}}+{\frac {2^{k-\beta }}{2^{k-1}}}+\epsilon =1+2^{\gamma -\alpha }+2^{1-\beta }+\epsilon$ where $\epsilon =-{\frac {1}{R_{1}}}$ in the $\left\lfloor \,\right\rfloor$ case and $\epsilon ={\frac {1}{2R_{1}}}$ in the $\left\lfloor \,\right\rceil$ case.
Setting $\beta =2$ and $\alpha =\gamma +1$ (or $\alpha =\gamma +2$ in the $\left\lfloor \,\right\rceil$ case) will always yield one check. In some cases, testing the bounds might yield a lower $\alpha$ and/or $\beta$ values.

## Small Barrett reduction

It is possible to perform a Barrett reduction with one less multiplication as follows
$a-\left[{\frac {a}{R}}\right]_{1}\,n$ where $R=2^{k}$ and $k$ is the bit-length of $n$
Every modulus can be written in the form $n=2^{k}-c=R-c$ for some integer $c$.
${\begin{aligned}a-\left[{\frac {a}{R}}\right]_{1}\,n&=a-{\frac {a-(a\,{\text{mod}}^{\left[\,\right]_{1}}\,R)}{R}}n\\&={\frac {aR-an+(a\,{\text{mod}}^{\left[\,\right]_{1}}\,R)n}{R}}\\&={\frac {ac+(a\,{\text{mod}}^{\left[\,\right]_{1}}\,R)n}{R}}\\&=n\left({\frac {a\,{\text{mod}}^{\left[\,\right]_{1}}\,R}{R}}+{\frac {ac}{Rn}}\right)\\&=n\left({\frac {a\,{\text{mod}}^{\left[\,\right]_{1}}\,R}{R}}+{\frac {a}{{\frac {R^{2}}{c}}-R}}\right)\end{aligned}}$
Therefore, reducing any $a<{\frac {R^{2}}{c}}-R$ for $\left[\,\right]_{1}=\left\lfloor \,\right\rfloor$ or any $|a|<\left({\frac {R^{2}}{c}}-R\right)/\,2$ for $\left[\,\right]_{1}=\left\lfloor \,\right\rceil$ yields one check.
From the analysis of the constraint, it can be observed that the bound of $a$ is larger when $c$ is smaller. In other words, the bound is larger when $n$ is closer to $R$.

## Barrett Division

Barrett reduction can be used to compute floor, round or ceil division $\left[{\frac {a}{n}}\right]$ without performing expensive long division. Furthermore it can be used to compute $\left[{\frac {ab}{n}}\right]$. After pre-computing the constants, the steps are as follows:
1. Compute the approximate quotient ${\tilde {q}}=\left[{\frac {a\,\left[{\frac {bR}{n}}\right]_{0}}{R}}\right]_{1}$
2. Compute the Barrett remainder ${\tilde {r}}=ab-{\tilde {q}}n$
3. Compute the quotient error $e=({\tilde {r}}-r)/n$ where $r=a\,{\text{mod}}^{\left[\,\right]}\,n$. This is done by subtracting a multiple of $n$ to ${\tilde {r}}$ until $r$ is obtained.
4. Compute the quotient $q={\tilde {q}}+e$
If the constraints for the Barrett reduction are chosen such that there is one check, then the absolute value of $e$ in step 3 cannot be more than 1. Using $\left[\,\right]_{0}=\left[\,\right]_{1}=\left\lfloor \,\right\rceil$ and appropriate constraints, the error $e$ can be obtained from the sign of ${\tilde {r}}$.

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