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
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 :
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 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:
funcreduce(auint)uint{q:=(a*m)>>k// ">> k" denotes bitshift by k.returna-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:
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
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]
^
ab
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.
ISBN978-3-540-18047-0.