[MUSIC] Hi, in this lesson we're going to study the operation or modular exponentiation. This operation is central for public key cryptography that we're going to study in the next module. It's properties allows for fast encryption and decryption for Alice and Bob and it is easy for them in one direction but it is hard to reverse for if who doesn't know something that either Alice or Bob knows. So first we're going to study how to compute this modular exponent quickly in this video and then in the next videos we're going to study the key properties, that make it useful for encryption and decryption. So modular exponentiation is the operation of computing b to the power e modular m. So we need to compute number c which is equal to b to the power of e modular m and how to do that? Well there is no need to actually compute the giant possibly giant number b to the power of e, and then divide it by m to get the remainder. Instead we can just start with 1 and then multiply this number which is at first 1 by me Immediately take the result modulo m, then multiply the result by b, and again take the result modulo m and so on and repeat all this e times and we'll get the remainder of b to the power of e modulo m because of the properties of remainders. Basically the remainder of product is equal to the product of remainders and this is the main property we are using here. So for example if b=7, e=4, m=11, basically we need to compute b to the power of four mod 11 and we start with assigning value of 1 to c and then we want to four times multiply the c by seven and take modular one. So first we get one times c which is then go to seven and then has a remainder of seven, modular eleven In the next step c already has value of 7, we multiply 7 by 7 get 49, 49 is 44 + 5, 11 divides 44, so the remainder is 5. On the next step c has value of 5 We multiply 5 by 7, get 35, it is 33 plus 2, so the remainder is 2 and finally, the c all ready contains value of 2, we multiplied it once more by 7, we get 14 and the remainder module 11 is 3. And finally we conclude that b to the power of e module m, which is 7 to the power of 4 module 11 is equal to 3. So this is the basically straightforward algorithm to compute modular expensation. Just start with assigning 1 to a value of c, and then we repeat e times, c is equal to c x b mod m. That's the whole algorithm. So we need just e multiplications and that's fast enough right? Well not always. What is b, e, and m are actually integers with thousands of digits and this is actually a practical case for cryptography. We need to work with really large integers so that if cannot decipher our messages. If b, e, and m or very small, then it would be very easy for if to decipher. But if we want our algorithm to work, then these numbers must be very big and the making e multiplications where e is a number with 1000 digits, well it won't finish in our life, or probably time of existence of this universe so we have to come up with something much, much faster than e multiplications. So can we actually do faster? Well let's first consider the case when e is a power of 2. e is equal to 2 to the power of k. What we can do then? Well in this example when b is again equal to 7 but e is equal to 128 which is 2 to the power of 7. Let's see what we can do. So first we can compute 7 to the power of 1 which is just 7, and then we can proceed with what is called squaring. So instead of computing powers of 7 as a second power, third power, or fourth power and so on we're going to square each time. So first we compute 7 squared, which is equal to 7 * 7 which is 49, and modulo 11 is equal to 5. Then given that 7 squared is equal to 5 modulo 11, we're going to compute 7 to the power of 4, as product of 7 squared times 7 squared or square of 7 squared. It is equal to 5 times 5 which is equal to 25, which is equal to 3 modulo 11. And on the next step we're going to compute 7 up to the power of 8 given 7 to the power of 4 equal to 3. So we are going to square this 7 to the power of 4. Get 3 times 3, which is equal to 9 modulo 11, which is just 9. And again we're going to compute 7 to the power of 16 by squaring 9 and get 4, compute 7 to the 32 by squaring 4 and get 5, then 7 to the 64 by squaring 5 and 3. And then finally 7 to the 128 by squaring 3 and getting 9. So actually we made just seven multiplications to compute seven to the power of 128 instead of 128 multiplications. That's significant improvement and in the general case the algorithm looks like following. We start with assigning value of b module m to c and then we repeat k times C assigned to c squared module m. And in the end the c will be equal to b to the power of 2 to the power of k which is equal to b to the power of e module m if e is in the form of 2 to the power of k. So instead of e multiplications, in this case we need just k which is equal to binary logarithm of e multiplication which is much much faster with large e. For example, if e contains 1,000 digits then k will be just on the order of a few thousand and not a number which is itself has a one thousand digits but just on the order of one thousand, and we can allow one thousand multiplication of course, or maybe a few thousand. So what if e is not a power of 2? What then can we do? Let's consider a following example. So we all ready know how to compute powers of 2 b module m, b, b squared, b to the 4th, b to the 8th, and so on. So how to compute b to the power of 13 module of m then? We can notice that 13 can be represented as sum of several powers of 2 because we know that any number can be rewritten in its binary form and so any number can be represented as a sum of some of the powers of 2. And then b to the power of 13 is just product of b to the power of 8 times b to the power 4 times b to the power of 1. So this idea of how we can actually compute b to the power 13 although 13 is not the power of 2 Itself. So in this example, we represent e as a sum of powers of 2 and the we can do this table of b to the power 1, b to the power of 2, b to the power of 4, b to the power of 8. All the powers of 2 which are less than or equal to 13. We do this with the squaring algorithm from the previous and we know all these remainders are correspondingly 7 5 3 and 9 and then we only need to multiply some of these remainders. In this case we need to multiply the remainders for, b to the power of 1, b to the power of 4, and b to the power of 8 which is 7 x 3 x 9, 7 x 3 = 21 which gives a remainder of 10 modular 11 and then 10 x 9 gives the remainder 2 modular 11 and then in the end, we conclude that b to the 13 module m is equal to 2. What we do in this case is we rewrite e in binary form. We compute b to the power of 2 to the power of k modulo m for all powers of 2 which are less than or equal to e. And then we multiply it together, the results for all powers of 2 in the binary representation of e. So first, we spend binary logarithm of e multiplications to compute all the b's to the power of 2, which are less than e. And then additionally, at most, binary logarithm of e multiplications to compute b to the power of e module and itself by multiplying all the needed B to the kth modulo m for all to the kth which are in the binary representation of e. So in total we will do at most two times binary logarithm of e multiplications. And to conclude, modular exponentiation can be computed using at most 2 binary algorithms of e multiplications instead of just e multiplications and for numbers e which have thousands of digits, this is just a few thousand instead of a huge number with thousand digits itself. To do that represent e in binary form we compute b to the power of k for all powers of 2 less than or equal to 2 using squaring and then compute finally b to the product of e mod m as a product of all needed b to the 2 to the power of k using binary representation of e. Next we are going to study the useful properties of modular exponization operation which allow us to safely encrypt and know that if probably won't be able to decrypt our cypher in any reasonable time. [MUSIC]