Barrett reduction explained

In modular arithmetic, Barrett reduction is a reduction algorithm introduced in 1986 by P.D. Barrett.^[1]

A naive way of computing

c = a \bmod n

would be to use a fast division algorithm. Barrett reduction is an algorithm designed to optimize this operation assuming

n is constant, and a<n ^{2} , replacing divisions by multiplications.

Historically, for values

a, b < n , one computed a b \bmod n by applyingBarrett reduction to the full product a b .Recently, it was shown that the full product is unnecessary if we can perform precomputation on one of the operands.^[2]

General idea

We call a function

\left[ \right]: R \to Z an integer approximation if |\left[z\right] - z| \leq 1 .For a modulus n and an integer approximation \left[\right] , we define mod ^{\left[\right]} n: Z \to ( Z /n Z ) asa mod ^{\left[\right]} n = a - \left[a / n\right] n .Common choices of \left[\right] are floor, ceiling, and rounding functions.

Generally, Barrett multiplication starts by specifying two integer approximations

\left[\right] _{0,} \left[\right] _{1} and computes a reasonably close approximation of ab \bmod n asa b - \left[ (a \left[ (b R)/(n) \right] _{0})/(R) \right] _{1} n ,

where

R is a fixed constant, typically a power of 2, chosen so that multiplication and division by R can be performed efficiently.

The case

b = 1 was introduced by P.D. Barrett ^[1] for the floor-function case \left[\right] _{0} = \left[\right] _{1} = \lfloor \rfloor .The general case for b 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.

Single-word Barrett reduction

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

b =1 and R =2 ^{k} .

When calculating

a \bmod n for unsigned integers, the obvious analog would be to use division by n :

func reduce(a uint) uint

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

1 /n with a value m/ 2 ^{k} because division by 2 ^{k} is just a right-shift, and so it is cheap.

In order to calculate the best value for

m given 2 ^{k} consider:(m)/(2 ^{k}) = (1)/(n) \Longleftrightarrow m = (2 ^{k})/(n)

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 used for unsigned arithmetic.

Thus we can approximate the function above with the following:

func reduce(a uint) uint

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 , 2 n) rather than [ 0 , n) as is generally required. A conditional subtraction will correct this:

func reduce(a uint) uint

Single-word Barrett multiplication

Suppose

b is known.This allows us to precompute \left\lfloor (b R)/(n) \right\rfloor before we receive a .Barrett multiplication computes a b , approximates the high part of a b with \left\lfloor (a \left\lfloor (b R)/(n) \right\rfloor)/(R) \right\rfloor n ,and subtracts the approximation.Since \left\lfloor (a \left\lfloor (b R)/(n) \right\rfloor)/(R) \right\rfloor n is a multiple of n ,the resulting value a b - \left\lfloor (a \left\lfloor (b R)/(n) \right\rfloor)/(R) \right\rfloor n is a representative of a b \bmod n .

Correspondence between Barrett and Montgomery multiplications

Recall that unsigned Montgomery multiplication computes a representative of

a b \bmod n as(a \left(b R \bmod n \right) + \left( a \left( - b R \bmod n \right) n ^{-1} \bmod R \right) n)/(R) .

In fact, this value is equal to

a b - \left\lfloor (a \left\lfloor (b R)/(n) \right\rfloor)/(R) \right\rfloor n .

We prove the claim as follows.

\begin{align} & & & a b - \left\lfloor (a \left\lfloor (b R)/(n) \right\rfloor)/(R) \right\rfloor n \\ & = & & a b - (a \left\lfloor (bR)/(n) \right\rfloor - \left( a \left\lfloor (bR)/(n) \right\rfloor \bmod R \right))/(R) n \\ & = & & \left( (a b R)/(n) - a \left\lfloor (bR)/(n) \right\rfloor + \left( a \left\lfloor (bR)/(n) \right\rfloor \bmod R \right) \right) (n)/(R) \\ & = & & \left( (a b R)/(n) - a (bR - \left(b R \bmod n \right))/(n) + \left( a \left\lfloor (bR)/(n) \right\rfloor \bmod R \right) \right) (n)/(R) \\ & = & & \left( (a \left(b R \bmod n \right))/(n) + \left( a \left\lfloor (bR)/(n) \right\rfloor \bmod R \right) \right) (n)/(R) \\ & = & & \left( (a \left(b R \bmod n \right))/(n) + \left( a \left( - b R \bmod n \right) n ^{-1} \bmod R \right) \right) (n)/(R) \\ & = & & (a \left(b R \bmod n \right) + \left( a \left( - b R \bmod n \right) n ^{-1} \bmod R \right) n)/(R) . \end{align}

Generally, for integer approximations

\left[\right] _{0,} \left[\right] _{1} ,we havea b - \left[ (a \left[ (b R)/(n) \right] _{0})/(R) \right] _{1} n = (a \left( b R mod ^{\left[\right] _{0}} n \right) + \left( a \left( - b R mod ^{\left[\right] _{0}} q \right) n ^{-1} mod ^{\left[\right] _{1}} R \right) n)/(R) .

Range of Barrett multiplication

We bound the output with

a b - \left\lfloor (a \left\lfloor (b R)/(n) \right\rfloor)/(R) \right\rfloor n = (a \left(b R \bmod n \right) + \left( a \left( - b R \bmod n \right) n ^{-1} \bmod R \right) n)/(\leq R) (a n + R n)/(R) = n \left( 1 + (a)/(R) \right) .

Similar bounds hold for other kinds of integer approximation functions.For example, if we choose

\left[\right] _{0} = \left[\right] _{1} = \left\lfloor\right\rceil , the rounding half up function,then we have \left| a b - \left\lfloor (a \left\lfloor (b R)/(n) \right\rceil)/(R) \right\rceil n \right| = \left| (a \left(b R mod ^{\pm} n \right) + \left( a \left( - b R mod ^{\pm} n \right) n ^{-1} mod ^{\pm} R \right) n)/(R) \right| \leq \left| (a (n)/(2) + (R)/(2) n)/(\right| = R) (n)/(2) \left( 1 + (|a|)/(R) \right).

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.^[3]

Barrett algorithm for polynomials

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

See also

• Montgomery reduction is another similar algorithm.

Sources

• Book: Bosselaers . A. . R. . Govaerts . J. . Vandewalle . Comparison of Three Modular Reduction Functions . Advances in Cryptology – Crypto'93 . 1993 . https://books.google.com/books?id=sqqoCAAAQBAJ&pg=PA175 . 175–186 . Springer . 3540483292 . 773 . Lecture Notes in Computer Science . Douglas R. . Stinson . 10.1.1.40.3779.
• Book: W. . Hasenplaugh . G. . Gaubatz . V. . Gopal . http://www.acsel-lab.com/arithmetic/arith18/papers/ARITH18_Hasenplaugh.pdf . Fast Modular Reduction . 18th IEEE Symposium on Computer Arithmetic(ARITH'07) . 2007 . 978-0-7695-2854-0 . 225–229 . 10.1109/ARITH.2007.18. 14801112 .

Notes and References

1. Book: Barrett . P. . Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor . 10.1007/3-540-47721-7_24 . Advances in Cryptology – CRYPTO' 86 . Lecture Notes in Computer Science . 263 . 311–323 . 1986 . 978-3-540-18047-0 .
2. Web site: Shoup . Victor. Number Theory Library.
3. Book: Alfred . Menezes . Paul . Oorschot . Scott . Vanstone . Handbook of Applied Cryptography . 1997 . 0-8493-8523-7 . registration .
4. Web site: Barrett reduction for polynomials . 2022-09-07 . www.corsix.org.