# Speeding up quotient determination in high-radix montgomery modular multiplication

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}$$?

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