# Montgomery Reduction

I'm taking a hardware cryptography class and working on a problem that focuses on Montgomery Reduction.

So by definition: Computing $a * b \text{ mod } N$

• Pick $R$, s.t. $R > N$, $gcd(R,N) = 1$
• Compute $N^{-1} \text{ mod }R$
• $a’ = a * R \text{ mod } N$
• $b’ = b * R \text{ mod } N$
• $c’ = (a’ * b’) * R^{-1} \text{ mod } N$
• $c = c’* R^{-1} \text{ mod } N$

Claim: $c ≡ a * b \text{ mod } N$

Proof: $c’R^{-1} ≡ (a’b’)R^{-1} R^{-1} ≡ (a’ * R^{-1}) * (b’ * R^{-1}) ≡ a * b \text{ mod } N$

If $R=2^k, x * R, ÷ R, \text{ mod } R$ are trivial an option to implement modular exponentiation.

Now I am ask to solve for this given the following 25 modulo 109 w.r.t. 128. The question I have is since I only have $a= 25$, does this mean there is no $b$ value? And if that is the case, I can ignore calculating the $b’ = b * R \text{ mod } N$ expression and also remove it from calculating the $c$ equation?

• You only need to do the Montgomery reduction after you do a multiplication of two values in Montgomery form. If you simply want to convert 25 to Montgomery form, then do 25 * R mod N. – user13741 Apr 24 '15 at 21:40
• Thank you for the explanation. I actually tried this approach, but wasn't successful. Maybe the question has a hidden point that I'm missing. Here is the question: Montgomery reduction of 25 modulo 109 with respect to 128 is – linos Apr 24 '15 at 22:22
• 25 * 128 mod 109 = 39. I really don't see what else they could be asking for. – user13741 Apr 24 '15 at 23:17
• I agree with you. I calculated the same result, but only doing it the long way. I will ask the prof. for an explanation. Thank You for your help. – linos Apr 25 '15 at 0:19
• So I received a bit more information on this problem. The problem is asking for the Montgomery Reduction, not computing axb(modN), so somehow I need to check the Montgomery reduction formulas. Also, another tip I received is that -N^-1=27. – linos Apr 25 '15 at 22:00

Answer is 30: $$T=25, N=109, -(N)^{-1} = 27, R=128$$ $$\Rightarrow T(R^{-1}) \bmod N$$ $$\Rightarrow m=T*(-N)^{-1} \bmod R \Rightarrow m= 25*27 \bmod 128 \Rightarrow m=35$$ $$\Rightarrow t= (T+m \cdot N)/R \Rightarrow (25+(35*109))/128 \Rightarrow t=30$$