Barrett reduction

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In modular arithmetic, Barrett reduction is a reduction algorithm introduced in 1986 by P.D. Barrett.[1] 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[edit]

Let be the inverse of as a floating point number. Then

where denotes the floor function. The result is exact, as long as m is computed with sufficient accuracy.

Single-word Barrett reduction[edit]

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(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 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 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 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 , 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(a uint) uint {
  q := (a * m) >> k
  a -= q * n
  if n <= a {
    a -= n
  }
  return a
}

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[edit]

Consider the case of when operating with 16-bit integers.

The smallest value of that makes sense is seven 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 equal to nine, , 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. (In practice the function happens to work for values up to 504.)

If we take then and so the maximum value of is 7387. (In practice the function happens to work until 7473.)

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[edit]

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

Multi-word Barrett reduction[edit]

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.[2]

See also[edit]

Montgomery reduction is another similar algorithm.

References[edit]

  1. ^ Barrett, P. (2006). "Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor". Advances in Cryptology — CRYPTO' 86. Lecture Notes in Computer Science. 263. pp. 311–323. ISBN 978-3-540-18047-0. doi:10.1007/3-540-47721-7_24. 
  2. ^ Menezes, Alfred; Oorschot, Paul; Vanstone, Scott. Handbook of Applied Cryptography. ISBN 0-8493-8523-7. 

Sources[edit]

  • Bosselaers, et al., "Comparison of Three Modular Reduction Functions," Advances in Cryptology-Crypto'93, 1993. [1]
  • W. Hasenplaugh, G. Gaubatz, V. Gopal, "Fast Modular Reduction", ARITH 18