1
$\begingroup$

I'm following well with using the shifting method to try out the Montgomery reduction (1st round). However, the computed result is actually equal to:

$$XYR^{-1} \bmod N$$ while the final goal is to obtain the result of

$$XY \bmod N$$

In order to get the final answer, I need to implement an extra step which is

$$(XYR^{-1})(R \bmod N) \bmod N$$

However, What if the product of $(XYR^{-1})(R \bmod N)$ giving me the large integer number?

In this case, how should leverage the same shifting method Montgomery reduction engine until I can obtain the final $Z = XY \bmod N$?

If I repeat the same Montgomery Reduction 2nd round using the product of $(XYR^{-1})(R \bmod N)$, I will just get back the same answer as $(XYR^{-1})$.

May I know what are the missing steps above?

$\endgroup$
9
  • $\begingroup$ If you switch to MontPro, life will be easy. See the bottom. $\endgroup$
    – kelalaka
    Dec 10 '20 at 6:45
  • $\begingroup$ Note that the Montgomery reduction/multiplication is always produced in $\bmod n$. $\endgroup$
    – kelalaka
    Dec 10 '20 at 6:50
  • $\begingroup$ @kelalaka , just want to understand is the solution of original question is still feasible with using existing shifting reduction method or it need to be resolved by using other alternative method like what you recommending? In fact, I'm reading your MontPro post multiple times but I still couldn't digest it well. It looks like the X or Y need to be converted to X bar or Y bar in order to using the function. $\endgroup$
    – Pi-Turn
    Dec 10 '20 at 8:54
  • 1
    $\begingroup$ @kelalaka, thanks for all time guidance. I see some light after the long day exploration. Allow me to verify my understanding with some hands on work. Hopefully It is correct :) $\endgroup$
    – Pi-Turn
    Dec 10 '20 at 14:29
  • 1
    $\begingroup$ @kelalaka, theory proved with hands-on with small integer hands on. Thank you very much....will proceed with big integer operation and so on....still long way to go. $\endgroup$
    – Pi-Turn
    Dec 12 '20 at 16:10

Your Answer

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

Browse other questions tagged or ask your own question.