Barrett reduction
In modular arithmetic, Barrett reduction is a reduction algorithm introduced in 1986 by P.D. Barrett.[1]
A naive way of computing
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.
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:
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.
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
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.