# 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

## 2 Answers

Consult the transcript from the class, there is an example he works through which is very similar to this problem. Fundamentally you're trying to solve the problem c = (T + T(-N^-1) (mod R)N)/R (mod N). I suggest creating an equation in Excel (or other tool of your choice). Test your equation using the inputs from the example problem (EXAMPLE INPUTS: T=69, N=109, R=128, -N^-1 = 27). When you're confident your equation is working for that (EXAMPLE PROBLEM SOLUTION = 61), then plug in the values for this problem. Hint: T = 25 for this problem.

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

• Even if this answer is correct (which I'm not going to spend any time checking), it doesn't really help the OP (or anyone else) understand how to solve problems like this. – Ilmari Karonen Mar 30 '18 at 0:51