Barrett reduction
In modular arithmetic, Barrett reduction is an algorithm designed to optimize the calculation of without needing a fast division algorithm. It replaces divisions with multiplications, and can be used when is constant and. It was introduced in 1986 by P.D. Barrett.
Historically, for values, one computed 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.
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 for the floor-function case.
The general case for can be found in NTL.
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.
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 uint
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 uint
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 uint
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 ofas
In fact, this value is equal to.
We prove the claim as follows.
Generally, for integer approximations,
we have
Range of Barrett multiplication
We bound the output withSimilar bounds hold for other kinds of integer approximation functions.
For example, if we choose, the rounding half up function,
then we have
It is common to select R such that so that the output remains within and, and therefore only one check is performed to obtain the final result between and. 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.
Barrett multiplication non-constant operands
The Barrett multiplication previously described requires a constant operand b to pre-compute ahead of time. Otherwise, the operation is not efficient. 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 as the product of the operands and set to. This leads to
A quick check on the bounds yield the following in case
and the following in case
Setting will always yield one check on the output. However, a tighter constraint on might be possible since is a constant that is sometimes significantly smaller than.
A small issue arises with performing the following product since is already a product of two operands. Assuming fits in bits, then would fit in bits and would fit in bits. Their product would require a 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:
where,,, and is the bit-length of.
Bound check in the case yields the following
and for the case yields the following
For any modulus and assuming, the bound inside the parenthesis in both cases is less than or equal:
where in the case and in the case.
Setting and will always yield one check. In some cases, testing the bounds might yield a lower and/or values.
Small Barrett reduction
It is possible to perform a Barrett reduction with one less multiplication as followsEvery modulus can be written in the form for some integer.
Therefore, reducing any for or any for yields one check.
From the analysis of the constraint, it can be observed that the bound of is larger when is smaller. In other words, the bound is larger when is closer to.
Barrett Division
Barrett reduction can be used to compute floor, round or ceil division without performing expensive long division. Furthermore it can be used to compute. After pre-computing the constants, the steps are as follows:- Compute the approximate quotient.
- Compute the Barrett remainder.
- Compute the quotient error where. This is done by subtracting a multiple of to until is obtained.
- Compute the quotient.