Let's see, we want to compute 68 times 57, modular 109.
So in this case, we have a equal to 68, b equals to 57, and N equal to 109.
So we pick a R which we want to have a power of 2 and greater than N.
So we pick R equal to 128, which is 2 to the power 7.
And then we compute an inverse and their mods R, which give us 27 101 here.
Because 109 times 101 equals to 1 modulo 128.
And when we put a negative sign here, it becomes 27.
So now we compute a prime, which is the modular multiplication between a and
R, in this case 68 times 128 which is 93.
And similarly, b prime will be defined as 57,
which is the value of b times R, which is 128.
And the result is 102.
And next we compute using the Montgomery reduction formula
to compute the Montgomery reduction of a prime times b prime.
So a prime times b prime which is the T here, plus the T times
negative N inverse which is 27 mod 128 times N,
which is 109, and then divided by R which is 128.
And if we simplify this, we realize the result is 178.
However, this is greater than N, which is 109.
So we subtract 109 from here.
We got the result, 69.
Next, we do another round of Montgomery Reduction of c prime.
So what we do is, we plug in the value of c prime into the formula here,
we've got c equal to c prime, which is 69,
plus 69 times 27 mod 128 times 101, 109 divided by 128.
And this give us a result of 61.