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?

  • 1
    $\begingroup$ 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. $\endgroup$
    – user13741
    Commented Apr 24, 2015 at 21:40
  • $\begingroup$ 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 $\endgroup$
    – linos
    Commented Apr 24, 2015 at 22:22
  • $\begingroup$ 25 * 128 mod 109 = 39. I really don't see what else they could be asking for. $\endgroup$
    – user13741
    Commented Apr 24, 2015 at 23:17
  • $\begingroup$ 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. $\endgroup$
    – linos
    Commented Apr 25, 2015 at 0:19
  • $\begingroup$ 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. $\endgroup$
    – linos
    Commented Apr 25, 2015 at 22:00

2 Answers 2


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

  • 3
    $\begingroup$ 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. $\endgroup$ Commented Mar 30, 2018 at 0:51
  • $\begingroup$ Can someone please help me understand how -(N)-1=27? $\endgroup$
    – smk
    Commented Dec 9, 2022 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.