# Correct modulus in Montgomery reduction

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?

## This question had a bounty worth +50 reputation from lovesh that ended yesterday. Grace period has ended

This question has not received enough attention.

• I'd give you a simpler way for their examples, prior to that but it's not the answer relevant to your question. – Roddy MacPhee Apr 18 at 21:05

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$$.