In this paper Simplifying Quotient Determination in High-Radix Modular Multiplication, the authors have proposed to replace the original modulus $M$ in Montgomery Multiplication $ABR^{-1} \bmod{M}$ to a new value $\tilde{M} = (M' \bmod{2^k}) M$, where $(-MM')\bmod{2^k}=1$.

The new modulus $\tilde{M}$ is used to improve the original Montgomery multiplication algorithm but also gives an output in the range of $[0, 2\tilde{M})$ instead of the range $[0, 2M)$ I actually need. However, the paper does not mention how to convert the result back to the desired range. What should I do to retrieve the actual result of $ABR^{-1} \bmod{M}$?

  • $\begingroup$ taking $\mod M$ doesn't enough? $\endgroup$ – kelalaka Feb 10 '19 at 20:22
  • $\begingroup$ Yes, it works. Thank you for your suggestion. $\endgroup$ – mksit May 22 '19 at 8:38
  • $\begingroup$ could you write an answer so that we can close this? $\endgroup$ – kelalaka May 23 '19 at 21:34

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.