Correct modulus in Montgomery reduction

102 Views Asked by At

I am trying to understand Montgomery reduction from this Wikipedia page (the algorithm matches in the original paper). For the reduction algorithm, the modular inverse of $R$ wrt. $N$ is calculated as $R^{-1}$. An N' is calculated from equation $R.R^{-1} - NN'$ such that $NN' = R.R^{-1} - 1$.
Now in the reduction algorithm in section "The REDC algorithm", $m$ and $t$ are computed as
m ← ((T mod R)N′) mod R
t ← (T + mN) / R

The m is expanded to be $TNN'$ and since $T.NN'$ becomes $T(R.R^{-1} - 1)$.

But how can this be done since m is calculated modulo R but $NN' = R.R^{-1} - 1$ holds true for modulo N?

1

There are 1 best solutions below

0
On

The m is expanded to be $TNN'$ and since $T.NN'$ becomes $T(R.R^{-1} - 1)$.

No, in the correctness proof we use only that $m\equiv TNN'\pmod R$ and the latter holds because $T\equiv (T\mod R) \pmod R $ and $(TN’\mod R) \equiv TN’ \pmod R$. Next, since $RR’-NN’=1$, we have $NN’\equiv –1\pmod R$ and finally we obtain $T+mN\equiv 0\pmod R$.