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 &gt; 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?
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.