# Montgomery Multiplication

## Algorithm
Consider prime field $\mathbb{F}_p$, select power of two $2^w$ such that $R=2^w > p$, we know that mod by R can be computed by bit shifting.

### Montgomery Form
For $x \in \mathbb{F}_p$, define Montgomery form of $x$ as,
$$\bar{x} = xR \pmod p$$

### Transform To Montgomery Form
Transforming $x$ to Montgomery form can be done by left-shift $x$ by $w$ and reduce modulo $p$. In practice, $x$ and $y$ are transformed to Montgomery form at the beginning of a computation, and transformed back at the end.

### Montgomery Form Arithmetic
Addition and subtraction in Montgomery form are the same as ordinary modular addition and subtraction because:
$$aR+bR=(a+b)R\\
aR−bR=(a−b)R$$

Define Montgomery multiplication $mont\_mult(\bar{x}, \bar{y})$ as,
$$\text{mont_mult}(\bar{x}, \bar{y}) = \bar{x} \bar{y} R^{-1} \pmod p$$
Where $R^{-1}$ is pre-computed from $R$ such that,
$$ RR^{-1} = 1 \pmod p$$

We know that,
$$\text{mont_mult}(\bar{x}, \bar{y}) = xyR \pmod p = \overline{xy}$$

### Transform From Montgomery Form
Finally, according to the definition of $\bar{x}$, to tranform montgormery form $\bar{x}$ back to normal form $x$, we multiply $\bar{x}$ by $2^{-w}$ and reduce modulo $p$
$$x = \bar{x} R^{-1} \pmod p$$

### Compute $\bar{x} \bar{y} R^{-1} \pmod p$
Computing muliply by $R^{-1}$ then divide by $p$ is slow. The `REDC` algorithm, aka Montgomery reduction, is used to simultaneously compute the product by $R^{-1}$ and reduce modulo $p$. Given $T=\bar{x} \bar{y}$,
$$\text{REDC}(T) = TR^{-1} \pmod p \\
= \bar{x} \bar{y}R^{-1} \pmod p = \text{mont_mult}(\bar{x}, \bar{y})$$

**Intuition**: Montgomery reduction focuses on making the number more divisible by $R$. It does this by adding a small multiple of $p$ which is chosen to cancel the residue modulo $R$ ($w$ bits of tailing $0$s). Dividing the result by $R$ (right-shift) yields a much smaller number that is nearly the reduction modulo $p$, and computing the reduction modulo $p$ requires only a final conditional subtraction.

// Given p, p', R, R', such that RR' - pp' = 1
// input T
// return TR' (mod p)
def reduce(T): 
    n = ((T mod R) p′) mod R
    // R|(T+np), a.k.a (T + mp) is divisible by R
    t = (T + np) / R  
    return (t >= p) ? (t - p) : p;

For correctness proof, please refer to [1].

Also note we can use $\text{redc}(xR^2)$ to fast calculate $\bar{x}$.

## Implementation: Multi-Precision Reduce (mpReduce)

The algorithm begins with a multiprecision integer $T$ and reduces it one word at a time. First an appropriate multiple of $p$ is added to make $T$ divisible by $2^w$. Then a multiple of $p$ is added to make $T$ divisible by $2^{2w}$, and so on. Eventually $T$ is divisible by $R$, and after division by $R$ the algorithm is in the same place as `REDC` was after the computation of $t$.

## References

[1] https://en.wikipedia.org/wiki/Montgomery_modular_multiplication

[2] https://hackmd.io/@chaosma/H1uSK1C35

[3] https://hackmd.io/@gnark/modular_multiplication

[4] https://www.microsoft.com/en-us/research/wp-content/uploads/1998/06/97Acar.pdf

###### tags: `msm` `zkp` `public`