Barrett Reduction

,The primary goal of Barrett reduction is to perform modular reduction efficiently. The standard calculation, xx/nnx - \lfloor x / n \rfloor \cdot n, involves a division (x/nx / n), which can be slow. Barrett reduction aims to replace this division.

The Core Idea

Barrett reduction uses multiplications, subtractions, and bit shifts (fast division by powers of 2) instead of a general division. It achieves this using a precomputed value based on the modulus nn to approximate the quotient value x/n\lfloor x / n \rfloor.

How it works

Setup and Precomputation

Suppose we are working with integers base bb. (Typically b=2b=2 in computers). Consider an integer kk such that bk>nb^k > n. Often, kk is chosen such that bkb^k is roughly n2n^2 (e.g., if nn fits in ww bits, k=2wk = 2w is common). Now, we precompute the value mm:

m=bk/nm = \lfloor b^k / n \rfloor

which acts as a scaled approximation of division by nn.

Approximating the Quotient

The true remainder is r=xqnr = x - q \cdot n, where the true quotient is q=x/nq = \lfloor x / n \rfloor. So in Barrett's method we would like to estimate qq without dividing xx by nn.

Consider the product xmx \cdot m. Substituting the definition of mm, we get:

xm=xbk/nx(bk/n)x \cdot m = x \cdot \lfloor b^k / n \rfloor\leq x\cdot (b^k/n)

Dividing both sides by bkb^k (which is a right shift by kk if b=2b=2):

(xm)/bk(xbk/n)/bk=x/n(x \cdot m) / b^k \le (x \cdot b^k / n) / b^k = x / n

This gives us the approximation to qq:

(xm)/bkx/n=q\lfloor(x \cdot m) / b^k\rfloor \le \lfloor x / n \rfloor = q

Let's denote this approximation as q^\hat{q}:

q^=(xm)/bkq\hat{q} = \lfloor (x \cdot m) / b^k \rfloor\le q

How Close is the Approximation?

Notice that we can write bk=bk/nn+rb^k=\lfloor b^k/n\rfloor \cdot n + r' for some remainder r<nr'<n. Solving for mm, we havem=(bkr)/nm=(b^k-r')/n. Replacing mm for the q^\hat{q} equation, we get:

q^=(xm)/bk=x(bkr)/nbk=(x/n)(xr/(nbk))\hat{q} = \lfloor (x \cdot m) / b^k \rfloor = \left\lfloor x \cdot \frac{(b^k - r')/n}{b^k} \right\rfloor = \lfloor (x/n) - (x \cdot r' / (n \cdot b^k)) \rfloor

Comparing q^\hat{q} to q=x/nq = \lfloor x/n \rfloor, the difference depends on the term (xr/(nbk))(x \cdot r' / (n \cdot b^k)), which is small if bkb^k is large enough relative to xx.

For example, if bk>n2b^k > n^2, then (xr/(nbk))<1(x \cdot r' / (n \cdot b^k)) < 1 which gives us a nice tight bound q1q^q-1\leq \hat{q} so we need only 1 subtraction at the worst case. If we choose a smaller kk such that bk>nb^k > n, q^\hat{q} can get as low as q2q-2, but typically we choose a large bk>n2b^k > n^2.

Final Reduction Algorithm

  • Precomputation (once for fixed nn):

    • Choose kk (e.g., k=2bitlength(n)k = 2 \cdot \mathsf{bitlength}(n)). We assume b=2b=2.

    • Calculate m=2k/nm = \lfloor 2^k / n \rfloor.

  • Reduction (for each xx):

    • Calculate q^=(xm)/2k\hat{q} = \lfloor (x \cdot m) / 2^k \rfloor (intermediate product xmx \cdot m might need k+bitlength(x/n)k + \mathsf{bitlength}(x/n) bits; often only the higher bits are needed since we do a kk bit-shift afterwards).

    • Calculate r^=xq^n\hat{r} = x - \hat{q} \cdot n.

    • Correction: while r^n\hat{r} \geq n, r^=r^n\hat{r}=\hat{r}-n

Cost Analysis of Modular Multiplication

Single-Precision case

Suppose the modulus nn has bit width of w<word_sizew< \mathsf{word\_size}. Then, the cost looks like:

  1. Computing x=ab:x=a\cdot b: multiplication of bitwidth w×w2ww\times w\rightarrow 2w .

  2. Computing xm:x\cdot m: multiplication of bitwidth 2w×(kw)w+k2w\times (k-w)\rightarrow w+k.

  3. Computing q^n:\hat{q}\cdot n: multiplication of bitwidth w×w2ww\times w\rightarrow 2w.

TODO(BATZORIG ZORIGOO): add multi-precision case

Written by BATZORIG ZORIGOO from A41

Last updated