Barrett reduction

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 formula_2 is constant, and formula_3, replacing divisions by multiplications.
General idea.
Let formula_4 be the inverse of formula_2 as a floating point number. Then
where formula_7 denotes the floor function. The result is exact, as long as formula_8 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 formula_9 using the method above, but with integers, the obvious analogue would be to use division by formula_2:
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, may not be a constant-time instruction on some CPUs. Thus Barrett reduction approximates formula_11 with a value formula_12 because division by formula_13 is just a right-shift and so it is cheap.
In order to calculate the best value for formula_14 given formula_13 consider:
In order for formula_14 to be an integer, we need to round formula_18 somehow. Rounding to the nearest integer will give the best approximation but can result in formula_12 being larger than formula_11, which can cause underflows. Thus formula_21 is generally used.
Thus we can approximate the function above with:
func reduce(a uint) uint {
 q := (a * m) » k // "» k" denotes bitshift by k.
 return a - q * n
However, since formula_22, the value of codice_1 in that function can end up being one too small, and thus codice_2 is only guaranteed to be within formula_23 rather than formula_24 as is generally required. A conditional subtraction will correct this:
func reduce(a uint) uint {
 q := (a * m) » k
 a -= q * n
 if n <= a {
 a -= n
 return a
Since formula_12 is only an approximation, the valid range of formula_26 needs to be considered. The error of the approximation of formula_11 is:
Thus the error in the value of codice_1 is formula_29. As long as formula_30 then the reduction is valid thus formula_31. The reduction function might not immediately give the wrong answer when formula_32 but the bounds on formula_26 must be respected to ensure the correct answer in the general case.
By choosing larger values of formula_34, the range of values of formula_26 for which the reduction is valid can be increased, but larger values of formula_34 may cause overflow problems elsewhere.
Example.
Consider the case of formula_37 when operating with 16-bit integers.
The smallest value of formula_34 that makes sense is formula_39 because if formula_40 then the reduction will only be valid for values that are already minimal! For a value of seven, formula_41. For a value of eight formula_42. Thus formula_43 provides no advantage because the approximation of formula_44 in that case (formula_45) is exactly the same as formula_46. For formula_47, we get formula_48, which is a better approximation.
Now we consider the valid input ranges for formula_39 and formula_47. In the first case, formula_51 so formula_31 implies formula_53. Since formula_26 is an integer, effectively the maximum value is 478. (In practice the function happens to work for values up to 504.)
If we take formula_47 then formula_56 and so the maximum value of formula_26 is 7387. (In practice the function happens to work until 7473.)
The next value of formula_34 that results in a better approximation is 13, giving formula_59. However, note that the intermediate value formula_60 in the calculation will then overflow an unsigned 16-bit value when formula_61, thus formula_39 works better in this situation.
Proof for range for a specific k.
Let formula_63 be the smallest integer such that formula_64. Take formula_65 as a reasonable value for formula_34 in the above equations. As in the code snippets above, let
Because of the floor function, formula_69 is an integer and formula_70. Also, if formula_71 then formula_72. In that case, writing the snippets above as an expression:
The proof that formula_72 follows:
If formula_71, then
Since formula_77 regardless of formula_26, it follows that
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".