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\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/503c8ba05db125f22fd715d5153961ace5913121)
would be to use a fast division algorithm. Barrett reduction is an algorithm designed to optimize this operation assuming
is constant, and
, replacing divisions by multiplications.
Historically, for values
, one computed
by applying Barrett reduction to the full product
. 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
an integer approximation if
. For a modulus
and an integer approximation
, we define
as
.
Common choices of
are floor, ceiling, and rounding functions.
Generally, Barrett multiplication starts by specifying two integer approximations
and computes a reasonably close approximation of
as
,
where
is a fixed constant, typically a power of 2, chosen so that multiplication and division by
can be performed efficiently.
The case
was introduced by P.D. Barrett [1] for the floor-function case
. The general case for
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
and
.
When calculating
for unsigned integers, the obvious analog would be to use division by
:
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
with a value
because division by
is just a right-shift, and so it is cheap.
In order to calculate the best value for
given
consider:
![{\displaystyle {\frac {m}{2^{k}}}={\frac {1}{n}}\;\Longleftrightarrow \;m={\frac {2^{k}}{n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/14d9b84af65b8907ad0857b41691e2dc32460340)
For
to be an integer, we need to round
somehow. Rounding to the nearest integer will give the best approximation but can result in
being larger than
, which can cause underflows. Thus
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
, the value of q
in that function can end up being one too small, and thus a
is only guaranteed to be within
rather than
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
is known. This allows us to precompute
before we receive
. Barrett multiplication computes
, approximates the high part of
with
, and subtracts the approximation. Since
is a multiple of
, the resulting value
is a representative of
.
Correspondence between Barrett and Montgomery multiplications
Recall that unsigned Montgomery multiplication computes a representative of
as
.
In fact, this value is equal to
.
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/50b8f9af510a8154054adf8f8588ae2401e64f81)
Generally, for integer approximations
, we have
.[3]
Range of Barrett multiplication
We bound the output with
.
Similar bounds hold for other kinds of integer approximation functions. For example, if we choose
, 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).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/809278a0d00518ca89658847a4b30aacb2c9f596)
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
- ^ a b 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.
- ^ a b Shoup, Victor. "Number Theory Library".
- ^ a b c 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
- ^ Menezes, Alfred; Oorschot, Paul; Vanstone, Scott (1997). Handbook of Applied Cryptography. ISBN 0-8493-8523-7.
- ^ "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.