Barrett reduction
In , Barrett reduction is a reduction algorithm introduced in 1986 by P.D. Barrett. A naive way of computing
c = a ,bmod, n. ,would be to use a fast . Barrett reduction is an algorithm designed to optimize this operation assuming n is constant, and a<n^2, replacing divisions by multiplications.
General idea
Let s=1/n be the inverse of n as a number. Then
a ,bmod, n = a-lfloor a srfloor nwhere lfloor x rfloor denotes the . The result is exact, as long as s 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 a ,bmod, n using the method above, but with integers, the obvious analogue would be to use division by n:
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 1/n with a value m/2^k because division by 2^k is just a right-shift and so is cheap.
In order to calculate the best value for m given 2^k consider:
frac{1}{n} = frac{n(frac{2^k}{n})} = frac{2^k} = frac{m}{2^k}In order for m to be an integer, we need to round {2^k}/{n} somehow. Rounding to the nearest integer will give the best approximation but can result in m/2^k being larger than 1/n, which can cause underflows. Thus m = lfloor {2^k}/{n} rfloor 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 m/2^k le 1/n, the value of q in that function can end up being one too small, and thus a is only guaranteed to be within [0, 2n) rather than [0, n) 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 m/2^k is only an approximation, the valid range of a needs to be considered. The error of the approximation of 1/n is:
e = frac{1}{n} - frac{m}{2^k}Thus the error in the value of q is ae. As long as ae < 1 then the reduction is valid thus a < 1/e. The reduction function might not immediately give the wrong answer when a ge 1/e but the bounds on a must be respected to ensure the correct answer in the general case.
By choosing larger values of k, the range of values of a for which the reduction is valid can be increased, but larger values of k may cause overflow problems elsewhere.
Example
Consider the case of n = 101 when operating with 16-bit integers.
The smallest value of k that makes sense is k = 7 because if 2^k < n then the reduction will only be valid for values that are already minimal! For a value of seven, m = lfloor 2^k / n rfloor = lfloor 128 / 101 rfloor = 1. For a value of eight m = lfloor 256 / 101 rfloor = 2. Thus k = 8 provides no advantage because the approximation of 1/101 in that case (2/256) is exactly the same as 1/128. For k = 9, we get m = 512 / 101 = 5, which is a better approximation.
Now we consider the valid input ranges for k = 7 and k = 9. In the first case, e = 1/n - m/2^k = 1/101 - 1/128 = 27/12928 so a < 1/e implies a < 478.81. Since a is an integer, effectively the maximum value is 478. (In practice the function happens to work for values up to 504.)
If we take k = 9 then e = 1/101 - 5/512 = 7/51712 and so the maximum value of a is 7387. (In practice the function happens to work until 7473.)
The next value of k that results in a better approximation is 13, giving 81/8192. However, note that the intermediate value ax in the calculation will then overflow an unsigned 16-bit value when 810 le a, thus k = 7 works better in this situation.
Proof for range for a specific k
Let k_0 be the smallest integer such that 2^{k_0}>n. Take k_0+1 as a reasonable value for k in the above equations. As in the code snippets above, let
q = leftlfloor frac{m a}{2^k} rightrfloorandr = a - q n.
Because of the , q is an integer and r equiv a pmod{n}. Also, if a < 2 ^ k then r < 2n. In that case, writing the snippets above as an expression:
a ,bmod, n = begin{cases} r & text{if } r<n \ r-n & text{otherwise} end{cases}The proof that r < 2n follows:
If a < 2 ^ k, then
frac{a}{2 ^ k} cdot (2 ^ k mod n) < nSince ncdotfrac{m a mod 2^k}{2^k} < n regardless of a, it follows that
frac{acdot (2 ^ k mod n)}{2 ^ k} + ncdotfrac{m a mod 2^k}{2^k} < 2na - left(a - frac{acdot (2 ^ k mod n)}{2 ^ k}right) + frac{(n cdot (m a mod 2^k))}{2^k} < 2na - left(leftlfloorfrac{2 ^ k}{n}rightrfloor cdot frac{n a}{2 ^ k}right) + frac{(n cdot (m a mod 2^k))}{2^k} < 2na - frac{m n a}{2 ^ k} + frac{(n cdot (m a mod 2^k))}{2^k} < 2na - left(frac{m a - (m a mod 2^k)}{2^k}right)cdot n < 2na - leftlfloorfrac{m a}{2 ^ k}rightrfloorcdot n < 2nr < 2n
Multi-word Barrett reduction
Barrett's primary motivation for considering reduction was the implementation of , 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.
See Also on BitcoinWiki
is another similar algorithm.