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]}

General idea

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]

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 ${\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}$:

funcreduce(auint)uint{q:=a/n// Division implicitly returns the floor of the result.returna-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:

funcreduce(auint)uint{q:=(a*m)>>k// ">> k" denotes bitshift by k.returna-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:

funcreduce(auint)uint{q:=(a*m)>>ka-=q*nifa>=n{a-=n}returna}

Single-word Barrett multiplication

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}$.

Correspondence between Barrett and Montgomery multiplications

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]

Range of Barrett multiplication

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 {\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 ${\displaystyle {\frac {a}{R}}<1}$ (or ${\displaystyle {\frac {\left|a\right|}{R}}<1}$ in the ${\displaystyle \left[\,\right]_{0}=\left[\,\right]_{1}=\left\lfloor \,\right\rceil }$  case) so that the output remains within ${\displaystyle 0}$ and ${\displaystyle 2n}$ (${\displaystyle -n}$ and ${\displaystyle n}$ resp.), and therefore only one check is performed to obtain the final result between ${\displaystyle 0}$ and ${\displaystyle 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 ${\displaystyle \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 ${\displaystyle a}$ as the product of the operands and set ${\displaystyle b}$ to ${\displaystyle 1}$. This leads to

${\displaystyle 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 ${\displaystyle \left[\,\right]_{0}=\left[\,\right]_{1}=\left\lfloor \,\right\rfloor }$ case

${\displaystyle {\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 ${\displaystyle \left[\,\right]_{0}=\left[\,\right]_{1}=\left\lfloor \,\right\rceil }$ case

${\displaystyle {\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 ${\displaystyle R>|a|}$ will always yield one check on the output. However, a tighter constraint on ${\displaystyle R}$ might be possible since ${\displaystyle R\,{\text{mod}}^{\left[\,\right]_{0}}\,n}$ is a constant that is sometimes significantly smaller than ${\displaystyle n}$.

A small issue arises with performing the following product ${\displaystyle a\,\left[{\frac {R}{n}}\right]_{0}}$ since ${\displaystyle a}$ is already a product of two operands. Assuming ${\displaystyle n}$ fits in ${\displaystyle w}$ bits, then ${\displaystyle a}$ would fit in ${\displaystyle 2w}$ bits and ${\displaystyle \left[{\frac {R}{n}}\right]_{0}}$ would fit in ${\displaystyle w}$ bits. Their product would require a ${\displaystyle 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:

${\displaystyle 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 ${\displaystyle R_{0}=2^{k-\beta }}$, ${\displaystyle R1=2^{\alpha +\beta }}$, ${\displaystyle R=R_{0}\cdot R_{1}=2^{k+\alpha }}$, and ${\displaystyle k}$ is the bit-length of ${\displaystyle n}$.

Bound check in the case ${\displaystyle \left[\,\right]_{0}=\left[\,\right]_{1}=\left[\,\right]_{2}=\left\lfloor \,\right\rfloor }$ yields the following

${\displaystyle {\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 ${\displaystyle \left[\,\right]_{0}=\left[\,\right]_{1}=\left[\,\right]_{2}=\left\lfloor \,\right\rceil }$ yields the following

${\displaystyle {\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 ${\displaystyle |a|<2^{k+\gamma }}$, the bound inside the parenthesis in both cases is less than or equal:

${\displaystyle 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 ${\displaystyle \epsilon =-{\frac {1}{R_{1}}}}$ in the ${\displaystyle \left\lfloor \,\right\rfloor }$ case and ${\displaystyle \epsilon ={\frac {1}{2R_{1}}}}$ in the ${\displaystyle \left\lfloor \,\right\rceil }$ case.

Setting ${\displaystyle \beta =2}$ and ${\displaystyle \alpha =\gamma +1}$ (or ${\displaystyle \alpha =\gamma +2}$ in the ${\displaystyle \left\lfloor \,\right\rceil }$ case) will always yield one check. In some cases, testing the bounds might yield a lower ${\displaystyle \alpha }$ and/or ${\displaystyle \beta }$ values.

Small Barrett reduction

It is possible to perform a Barrett reduction with one less multiplication as follows

${\displaystyle a-\left[{\frac {a}{R}}\right]_{1}\,n}$ where ${\displaystyle R=2^{k}}$ and ${\displaystyle k}$ is the bit-length of ${\displaystyle n}$

Every modulus can be written in the form ${\displaystyle n=2^{k}-c=R-c}$ for some integer ${\displaystyle c}$.

${\displaystyle {\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 ${\displaystyle a<{\frac {R^{2}}{c}}-R}$ for ${\displaystyle \left[\,\right]_{1}=\left\lfloor \,\right\rfloor }$ or any ${\displaystyle |a|<\left({\frac {R^{2}}{c}}-R\right)/\,2}$ for ${\displaystyle \left[\,\right]_{1}=\left\lfloor \,\right\rceil }$ yields one check.

From the analysis of the constraint, it can be observed that the bound of ${\displaystyle a}$ is larger when ${\displaystyle c}$ is smaller. In other words, the bound is larger when ${\displaystyle n}$ is closer to ${\displaystyle R}$.

Barrett Division

Barrett reduction can be used to compute floor, round or ceil division ${\displaystyle \left[{\frac {a}{n}}\right]}$ without performing expensive long division. Furthermore it can be used to compute ${\displaystyle \left[{\frac {ab}{n}}\right]}$. After pre-computing the constants, the steps are as follows:

1. Compute the approximate quotient ${\displaystyle {\tilde {q}}=\left[{\frac {a\,\left[{\frac {bR}{n}}\right]_{0}}{R}}\right]_{1}}$

2. Compute the Barrett remainder ${\displaystyle {\tilde {r}}=ab-{\tilde {q}}n}$

3. Compute the quotient error ${\displaystyle e=({\tilde {r}}-r)/n}$ where ${\displaystyle r=a\,{\text{mod}}^{\left[\,\right]}\,n}$. This is done by subtracting a multiple of ${\displaystyle n}$ to ${\displaystyle {\tilde {r}}}$ until ${\displaystyle r}$ is obtained.

4. Compute the quotient ${\displaystyle q={\tilde {q}}+e}$

If the constraints for the Barrett reduction are chosen such that there is one check, then the absolute value of ${\displaystyle e}$ in step 3 cannot be more than 1. Using ${\displaystyle \left[\,\right]_{0}=\left[\,\right]_{1}=\left\lfloor \,\right\rceil }$ and appropriate constraints, the error ${\displaystyle e}$ can be obtained from the sign of ${\displaystyle {\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. ^[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

1. Barrett, P. (1986). "Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor". Advances in Cryptology – CRYPTO' 86. Lecture Notes in Computer Science. Vol. 263. pp. 311–323. doi:10.1007/3-540-47721-7_24. ISBN   978-3-540-18047-0.
2. Shoup, Victor. "Number Theory Library".
3. Becker, Hanno; Hwang, Vincent; Kannwischer, Matthias J.; Yang, Bo-Yin; Yang, Shang-Yi (2021), "Neon NTT: Faster Dilithium, Kyber, and Saber on Cortex-A72 and Apple M1", Transactions on Cryptographic Hardware and Embedded Systems, 2022 (1): 221–244, doi: 10.46586/tches.v2022.i1.221-244
4. Menezes, Alfred; Oorschot, Paul; Vanstone, Scott (1997). Handbook of Applied Cryptography (5th ed.). CRC Press. doi:10.1201/9780429466335. ISBN   0-8493-8523-7.
5. "Barrett reduction for polynomials". www.corsix.org. Retrieved 2022-09-07.

Sources

• Bosselaers, A.; Govaerts, R.; Vandewalle, J. (1993). "Comparison of Three Modular Reduction Functions". In Stinson, Douglas R. (ed.). Advances in Cryptology – Crypto'93. Lecture Notes in Computer Science. Vol. 773. Springer. pp. 175–186. CiteSeerX   10.1.1.40.3779 . ISBN   3540483292.
• Hasenplaugh, W.; Gaubatz, G.; Gopal, V. (2007). "Fast Modular Reduction" (PDF). 18th IEEE Symposium on Computer Arithmetic(ARITH'07). pp. 225–229. doi:10.1109/ARITH.2007.18. ISBN   978-0-7695-2854-0. S2CID   14801112.