1
$\begingroup$

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?

$\endgroup$

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

This question has not received enough attention.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.