Modular Arithmetic

Modular multiplication

Problem: $a,b\in {\mathbb{Z}}_N$, calculate $a.b\mathrm{mod}N$

Montgomery multiplication

Aim is to add a multiple of $N$ to $c$ such that, it becomes divisible by $R$. Choose different divisor $R>N$ such that,

$$gcd(R,N)=1⟹\exists R^{-1}:R{R}^{-1}\equiv 1⟹\exists N^{\prime }<R:R{R}^{-1}=N{N}^{\prime }+1$$

i.e. $N^{\prime }$ is negative inverse of $N$. Generally, R is chosen to be power of 2, like $2^{\omega }$, so that division by R is just right bit shift by $\omega$.

$$\begin{array}{rl}\bar{a}& =aR\mathrm{mod}N\\ \bar{b}& =bR\mathrm{mod}N\\ c& =\bar{a}\bar{b}\mathrm{mod}N=[aR][bR]\equiv abR.R\equiv [abR].R\\ \bar{c}& =redc(c)=c{R}^{-1}\mathrm{mod}N\end{array}$$

Note: $0\le c<N.N<R.N$. Let’s understand how $redc$ works:

$$\begin{array}{rl}R.R^{-1}& =N.N^{\prime }+1\\ c.N^{\prime }\mathrm{mod}R& =c.\frac{R.R^{-1}-1}{N}\mathrm{mod}R=c.N^{\prime }\mathrm{mod}R\\ k& =c.N^{\prime }\mathrm{mod}R\\ t& =\frac{c+kN}{R}\\ t\mathrm{mod}N& =c.R^{-1}\mathrm{mod}N\end{array}$$

Cost: 3 big-int mults. $3n^2$ integer multiplication.

Prove: $R|(c+kN)$ and $\frac{c+kN}{R}<2N$:

$$\begin{array}{c}c\end{array}$$

Multi precision, radix $r$

Choose: $R:2^{nr}$, and $b=2^r$

$$\begin{array}{ccc}A& :a_0+a_{1}b+\dots +a_{n-1}{b}^{n-1}& ={\sum }_0^{n-1}{a}_i{b}^i\\ c& :\bar{a}\bar{b}{R}^{-1}& ={\sum }_{i=0}^{r-1}{x}_{i}y{2}^{ir}{2}^{-nr}\end{array}$$

1. Initialize $t\leftarrow AB$
2. update t every loop $i:0\to n-1$, such that $b^{i+1}|t$
   1. $k_i=t_i.b^i.N_0^{\prime }\mathrm{mod}b$
   2. $t=t+k_i.N$
3. divide R: $t=t/R$

Prove: $b^{i+1}|t$

$$T^{(i)}=AB+\sum _i^{j=0}{k}_{i}N$$

We’ll prove this using induction. So,

$$\begin{array}{c}{T}^{(0)}=AB+k_{0}N=AB+t_0{b}^0{N}_0^{\prime }(N_0+N_{1}b+\dots +N_{r-1}{b}^{r-1})=A{B}_0(1+N_0^{\prime }{N}_0)+b(\dots )\end{array}$$

Thus, $b$ divides $T_0$. similarly, let’s formulate $T^{(i)}$:

$$\begin{gathered} \begin{array}{c}{T}^{(i)}=(0,\cdots ,0,T_i^{(i-1)},\cdots )+m_{i}N{b}^i=T_i^{(i-1)}{b}^i+T_i^{(i-1)}{n}_0^{\prime }{n}_0{b}^i+b^{i+1}(\cdots ) \\ =T_i^{(i-1)}{b}^i(1+n_0^{\prime }{n}_0)+b^{i+1}(\cdots )\end{array} \end{gathered}$$

understand above from Montgomery modular multiplication

Instead of updating $t$ every loop, we’ll split and update $t_i$ and shift $t$ by a word after each loop, which is essentially dividing by $R$. Explaining CIOS algorithm from

Resources

• Montgomery Reduction
• Faster big-integer modular multiplication for most moduli
• Montgomery modular multiplication
• cliff’s personal blog: montgomery multiplication
• montgomery: Fast MSM in WebAssembly
• EdMSM
• HPC: Montgomery
• Ingonyama: modular multiplication
• montgomery-reduction algorithm
• Barret reduction