In modular arithmetic, Barrett reduction is a reduction algorithm introduced in 1986 by P.D. Barrett. 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.
General idea
Let be the inverse of as a floating point number. Then where denotes the floor function. The result is exact, as long as is computed with sufficient accuracy.
Single-word Barrett reduction
Barrett initially considered an integer version of the above algorithm when the values fit into machine words. When calculating using the method above, but with integers, the obvious analogue would be to use division by : func reduce uint
However, division can be expensive and, in cryptographic settings, may not be a constant-time instruction on some CPUs. Thus Barrett reduction approximates with a value because division by is just a right-shift and so is cheap. In order to calculate the best value for given consider: In order for to be an integer, we need toround somehow. Rounding to the nearest integer will give the best approximation but can result in being larger than, which can cause underflows. Thus is generally used. Thus we can approximate the function above with: 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
Since is only an approximation, the valid range of needs to be considered. The error of the approximation of is: Thus the error in the value of q is. As long as then the reduction is valid thus. The reduction function might not immediately give the wrong answer when but the bounds on must be respected to ensure the correct answer in the general case. By choosing larger values of, the range of values of for which the reduction is valid can be increased, but larger values of may cause overflow problems elsewhere.
Example
Consider the case of when operating with 16-bit integers. The smallest value of that makes sense is because if then the reduction will only be valid for values that are already minimal! For a value of seven,. For a value of eight. Thus provides no advantage because the approximation of in that case is exactly the same as. For, we get, which is a better approximation. Now we consider the valid input ranges for and. In the first case, so implies. Since is an integer, effectively the maximum value is 478. If we take then and so the maximum value of is 7387. The next value of that results in a better approximation is 13, giving. However, note that the intermediate value in the calculation will then overflow an unsigned 16-bit value when, thus works better in this situation.
Proof for range for a specific k
Let be the smallest integer such that. Take as a reasonable value for in the above equations. As in the code snippets above, let
and
.
Because of the floor function, is an integer and. Also, if then. In that case, writing the snippets above as an expression: The proof that follows: If, then Since regardless of, it follows that
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.
