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