0:09

Let R and N be two integers that are relatively prime to each other.

Â And R is greater than N.

Â For any integer T, which is greater than or equal to 0 and less than the product

Â of N and R, the Montgomery reduction of T mod N with respect to R

Â is defined as the modular multiplication of T and R inverse mod N.

Â Where R inverse it the multiplicative inverse of R mod N.

Â Which means R times R inverse equal to one, mod N.

Â From this definition, we see that Montgomery reduction is nothing but

Â a modular multiplication and, mod, mod N.

Â The following algorithm actually tells us there are some other ways

Â to compute this quantity.

Â 1:03

We start with some modular modification between T and

Â the negative and inverse mod R.

Â And we call this value m.

Â Next, we add T and

Â m times N, and the sum will be divided by R.

Â 1:21

The quotient, t, will be compared with N.

Â If N is less than or equal to t, N will be subtracted from t,

Â and the final value of t will be report, reported as the Montgomery reduction.

Â 1:44

The goal of the algorithm is to compute the Montgomery reduction,

Â which is the modular multiplication and the mod N.

Â But in this algorithm you don't see any modular multiplication in the mod N.

Â What we do see is one modular multiplication in the mod R.

Â 2:12

Now let's prove this result t is indeed the Montgomery reduction.

Â To prove this is true we have to show two things.

Â First t times R must equal to capital T and the mod N,

Â and second, t must be between zero and N.

Â To see the first equation, we start with the definition of t,

Â and we multiply both sides by capital R.

Â This gives us t times R equal to T plus m times N.

Â When we do a mod N operation, the second term disappeared, so

Â the only thing left is T as required.

Â 2:56

If t is obtained by subtracting N from the original t,

Â we see this equation still holds.

Â Because it is entered a (mod N) operation.

Â So subtracting or adding a N doesn't change anything.

Â 3:12

To see the second condition which tells the range of t,

Â we start with the definition of m.

Â So, m is defined as the remainder of T times megative N

Â inverse divided by R, or the mod R operation.

Â From the definition of remainder or

Â mod operation we know m must be between zero and R.

Â So if we multiply this inequality by N, we know zero is less than or

Â equal to m times N and less than N times R.

Â This combined with the range, we select a T, so we have the following inequality.

Â T plus m times N must be greater than or equal to 0,

Â and also less than one N times R plus another N times R,

Â so total less than 2 times N times R.

Â 4:11

So if we divided this inequality by R, what we get is T plus

Â m times N divided by R will fall into the range of zero and 2 times N.

Â And this quotient, it is exactly the definition of T.

Â So we know that one T is less than, less than N, it is what we need.

Â And if t is greater than or equal to N, and following the definition,

Â N will be subtracted from t, again putting the, the value of t into the right range.

Â 4:47

This completes the proof.

Â It tells us, indeed, the Montgomery reduction algorithm does give

Â us the correct answer from Mon, from Montgomery reduction.

Â 4:59

When we plug in the definition of m into the equation for

Â t, indeed we get the Montgomery Reduction algorithm's formula.

Â Where the reduction equal to T plus T times negative N inverse mod R

Â times N divided by R.

Â And pay attention here, at the end we have a mod n operation.

Â And remember in the procedure we do have mod N.

Â So this mod N here is actually a shorthand in the notation.

Â 5:29

Remember, when we do this division divided by R,

Â we know that if the quotient is less than N we don't do anything.

Â If the quotient of t is greater than or equal to N, we subtract the N from t.

Â This is exactly the modular operation.

Â So that is why we use mod N as a short-handed notation to indicate this

Â condition and this subtraction operation.

Â 5:56

Next we'll show how we can use Montgomery Reduction to simplify,

Â or to speed up, the computation of modular multiplication, of modular multiplication.

Â So to apply Montgomery reduction, so let's pick integer R,

Â which is greater than N and relatively prime to N.

Â And then we compute the following quantities in order.

Â First, we compute an inverse mod N, and

Â then we do the modular multiplication between a and R mod N,

Â and similarly we do another modular multiplication between b and R mod N.

Â And the last of the two operations, are the Montgomery reductions.

Â First, we compute the Montgomery reduction of a prime times b prime

Â mod N, with respect to R, and then this new result is called c prime.

Â We can calculate the Montgomery reduction of c prime.

Â 7:30

And because this multiplication, they are commutative, so

Â we pair up a prime with one of the R inverse to get a prime times R inverse,

Â which is a, following the definition here.

Â And similarly, b prime times R prime gives us b,

Â which shows this is indeed the modular multiplication.

Â So what we see here is we pick this R satisfies only two conditions.

Â First R must be greater than N.

Â And second, R and N must be relative prime to each other.

Â And so, as long as these two condition are satisfied, we can pick any R we want.

Â 8:16

So when R happens to be a power of two.

Â So what we know that in digital computer, the multiplication of R in

Â this case will be a shift of k back to the left by k bits.

Â And the division by R with the modular

Â R operation will be a shift to the right by k bits.

Â So all these operations will be trivial operations.

Â So that is why, if we are following the Montgomery reduction algorithm and

Â pick R as a power of two, then this gives us

Â a great potential to optimize the modular exponentiation.

Â So now let's see example to see how this can be performed.

Â 9:05

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.

Â 11:28

To verify this indeed is the result, the correct result, so

Â we used the naive, straightforward multiplication and modular.

Â So when we multiply 68 and 57, we got 3876.

Â And then when we do a mod 109, we got 61.

Â Which is exactly the same value here.

Â