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 \left|{\frac {a{\frac {n}{2}}+{\frac {R}{2}}n}{R}}\right|={\frac {n}{2}}\left(1+{\frac {|a|}{R}}\right).}$

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, "Neon NTT: Faster Dilithium, Kyber, and Saber on Cortex-A72 and Apple M1", Transactions on Cryptographic Hardware and Embedded Systems, 2022 (1): 221–244
4. Menezes, Alfred; Oorschot, Paul; Vanstone, Scott (1997). Handbook of Applied Cryptography . 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.