Jump to content

Barrett reduction

From Wikipedia, the free encyclopedia

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.

Historically, for values , one computed by applying Barrett reduction to the full product . Recently, it was shown that the full product is unnecessary if we can perform precomputation on one of the operands.[2][3]

General idea[edit]

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 [1] for the floor-function case . The general case for can be found in NTL.[2] 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.[3]

Single-word Barrett reduction[edit]

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(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, 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(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 a >= n {
        a -= n
    return a

Single-word Barrett multiplication[edit]

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

Recall that unsigned Montgomery multiplication computes a representative of as


In fact, this value is equal to .

We prove the claim as follows.

Generally, for integer approximations , we have


Range of Barrett multiplication[edit]

We bound the output with .

Similar bounds hold for other kinds of integer approximation functions. For example, if we choose , the rounding half up function, then we have

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

Barrett algorithm for polynomials[edit]

It is also possible to use Barrett algorithm for polynomial division, by reversing polynomials and using X-adic arithmetic.[5]

See also[edit]


  1. ^ a b Barrett, P. (1986). "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. Vol. 263. pp. 311–323. doi:10.1007/3-540-47721-7_24. ISBN 978-3-540-18047-0.
  2. ^ a b Shoup, Victor. "Number Theory Library".
  3. ^ a b c Becker, Hanno; Hwang, Vincent; Kannwischer, Matthias J.; Yang, Bo-Yin; Yang, Shang-Yi, "Neon NTT: Faster Dilithium, Kyber, and Saber on Cortex-A72 and Apple M1", Transactions on Cryptographic Hardware and Embedded Systems, 2022 (1): 221–244
  4. ^ Menezes, Alfred; Oorschot, Paul; Vanstone, Scott (1997). Handbook of Applied Cryptography. ISBN 0-8493-8523-7.
  5. ^ "Barrett reduction for polynomials". www.corsix.org. Retrieved 2022-09-07.