In modular arithmetic, Barrett reduction is an algorithm designed to optimize the calculation of
by applying Barrett reduction to the full product
In 2021, Becker et al. showed that the full product is unnecessary if we can perform precomputation on one of the operands.
Generally, Barrett multiplication starts by specifying two integer approximations
is a fixed constant, typically a power of 2, chosen so that multiplication and division by
[4] 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] Barrett initially considered an integer version of the above algorithm when the values fit into machine words.
for unsigned integers, the obvious analog would be to use division by
: 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.
Rounding to the nearest integer will give the best approximation but can result in
, the value of q in that function can end up being one too small, and thus a is only guaranteed to be within
Recall that unsigned Montgomery multiplication computes a representative of
Similar bounds hold for other kinds of integer approximation functions.
, the rounding half up function, then we have It is common to select R such that
), and therefore only one check is performed to obtain the final result between
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.
The Barrett multiplication previously described requires a constant operand b to pre-compute
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
A small issue arises with performing the following product
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:
, the bound inside the parenthesis in both cases is less than or equal:
In some cases, testing the bounds might yield a lower
Barrett reduction can be used to compute floor, round or ceil division
If the constraints for the Barrett reduction are chosen such that there is one check, then the absolute value of
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.