Modular Arithmetic II - Barrett

The series of Modular Arithmetic will introduce readers to basic modular arithmetic knowledge, and some classical algorithms. I plan to divide it into 3 parts: Montgomery, Barrett, and Look-Up Table. Since I don't have an ECE background, all of them will mainly focus on mathematical perspectives. This is the 2nd part of the series - Barrett and its variants.

Barrett is another way to calculate modular multiplication, which uses a different method for investigating the problem. This article will have structure as below:

• Barrett multiplication
  
  • Interpretation 1
    
  • Interpretation 2
    
• Bit analysis
  
• Comparison with Montgomery
  ## Barrett Multiplication

Interpretation 1

(Disclaimer: I quite forget where I found the derivation of interpretation 1. It's probably from Nayuki's Barrett post plus some of my own understandings.)

Goal: \(res = z \bmod q\), where \(z \in [0, q\cdot 2^k)\), modulus \(q\) fits in \(k\) bits.

Different from Montgomery, Barrett uses an approximation approach to solve this problem. We first start by looking at native calculation of modular arithmetic: \[ res = z \bmod q = z - q\cdot\lfloor\frac{z}{q}\rfloor = z - qp, \] where \(p = \lfloor\frac{z}{q}\rfloor\).

As mentioned in Part I, it is difficult for a computer to directly calculate \(p\). Thus, we consider replacing this \(p\) by an approximate \(\hat{p}\), and this \(\hat{p}\) should be easy to calculate.

We start by adding parameters \(\alpha, \beta\): \[ \frac{z}{q} = \frac{z}{2^{k+\beta}}\cdot \frac{2^{k+\alpha}}{q}\cdot \frac{1}{2^{\alpha-\beta}} = \frac{\frac{z}{2^{k+\beta}}\cdot \frac{2^{k+\alpha}}{q}}{2^{\alpha-\beta}}. \] We can let \(\hat{p}\) be the following form: \[ 0 \leq \hat{p} = \lfloor\frac{\lfloor\frac{z}{2^{k+\beta}}\rfloor\cdot\lfloor \frac{2^{k+\alpha}}{q}\rfloor}{2^{\alpha-\beta}}\rfloor \leq p \] Observe:

1. \(\lfloor\frac{z}{2^{k+\beta}}\rfloor\): easy to calculate by bit shifting.
2. \(\mu \coloneqq \lfloor \frac{2^{k+\alpha}}{q}\rfloor\): can be pre-calculated since we have known modulus \(q\).
3. \(\lfloor\frac{\cdots}{2^{\alpha-\beta}}\rfloor\): easy to calculate by bit shifting.

We only need to prove that \(\hat{p}\) is very close to \(p\) and obtain how close it is.

Let: \[ \begin{aligned} b &= \frac{z}{2^{k+\beta}} - \lfloor\frac{z}{2^{k+\beta}}\rfloor \in [0,1), \\ a &= \frac{2^{k+\alpha}}{q} - \lfloor \frac{2^{k+\alpha}}{q} \rfloor \in [0,1). \end{aligned} \] Since \(a,b <1\), \(p\) can be upper bounded by: \[ \begin{aligned} p &= \lfloor \frac{\frac{z}{2^{k+\beta}}\cdot \frac{2^{k+\alpha}}{q}}{2^{\alpha-\beta}} \rfloor = \lfloor\frac{(\lfloor\frac{z}{2^{k+\beta}}\rfloor+b) \cdot (\lfloor \frac{2^{k+\alpha}}{q}\rfloor+a)}{2^{\alpha-\beta}}\rfloor\\ &\leq \lfloor \frac{\lfloor\frac{z}{2^{k+\beta}}\rfloor \cdot \mu}{2^{\alpha-\beta}} + \frac{\lfloor\frac{z}{2^{k+\beta}}\rfloor + \mu + 1}{2^{\alpha-\beta}} \rfloor. \end{aligned} \] Apparently the first term is our approximation, so we want the second term to be small enough, better be 1 or 2, then we can bound \(p\) by \(\hat{p}\) and \(\hat{p}\) plus something.

(to be done)