If we have unrealistically small numbers, then we can answer questions like, what is three raised to the fifth power in a mod 143 world, by carrying out the arithmetic directly and reducing it by the modulus. But, what about 12,345 raised to the 6,789th power, in that same mod 143 world. This is well beyond the capabilities of any calculators and most programming languages unless you use arbitrary precision arithmetic, also known as a big number library. Even then, we are talking about a number that has nearly 28,000 digits and our calculations must be exact, since we are off by even one, then we get the wrong modulus. Furthermore, this sure seems like a lot of work to get a number that at the end of the day is going to be strictly less than 143. In this lesson, we develop a very powerful way of performing modular exponentiation, that allows us to solve this problem by hand in a matter of minutes to get the an answer of 125. The first thing we can do is reduce the base by the modulus, which gets us down to a number that is somewhat over 11,000 digits. Which I guess is quite an improvement, but not really enough to help. We saw in a prior lesson that we can't reduce the exponent by the modulus, because it lives in a different modular world. That world is the so-called totient of the modulus, which is given by Euler's phi function. Which is the number of positive integers less than the modulus that are relatively prime to it. We'll see why this is the case in another lesson and how to calculate the totient. But, for now I'll just tell you that the notion of 143 happens to be 120. Using this knowledge, we get down to 116 digit number, which is a humongous improvement. It even puts it in the range of being able to do by hand, if we really, really had to. But it would take a very long time and be very error prone. Important to note that this still requires a big number library. Yes, we can represent an approximation of this number using floating point numbers, but they are only approximations. Remember that our calculations must be exact. This is still a lot of work to get a result that has at most three digits. Recognizing that exponentiation is just repeated multiplication, we can pull out the first two factors, multiply them together and reduce by the modulus to give us a running product. We can then pull out the next factor, multiply it by the running product and reduce by the modulus. We then repeat this process until our exponent becomes zero. Thus the number of times we need to repeat this loop is on the order of the exponent, which can be nearly as large as the modulus. Even more significant, the largest number we ever have to work with is less than the square of the modulus. So now to get our three digit result, we only have to be able to work with five digit numbers. While this is an almost unimaginably huge improvement, it is nowhere near good enough for the kind of numbers we routinely work with in cryptography. Currently, the US government recommends an RSA modulus of 2048 bits, for unclassified data. That's a modulus with over 600 decimal digits. Recall that the number of atoms in the universe, only has about 80 digits. So, using this method to perform exponentiation is useless long before we get to this scale. We must do much better. Fortunately, we can. A very simple method can reduce the number of iterations from the order of the modulus, to the order of the log of the modulus. Which equates to the number of bits in the exponent instead of the exponent itself. For 2048 bit moduli, this means just over 2,000 iterations maximum. Something that can be carried out by smart cards and chips credit cards, such is the power of algorithms that are of algorithmic complexity. The idea behind our new approach is that when numbers with the same base are multiplied, the exponent add. Not only is 47 to the 34th power easier to compute. And of course, we reduce it by mode 143 as we go. But, once we have it, we only have to square it and multiply by 47 to get our answer. We could recursively apply this algorithm first to get 47 to 34th, using the same approach. But, a more systematic approach is to come at it from the opposite direction. We can calculate 47 to the first power mod 143 trivially. If we square this, we get that the square of 47 is congruent to 64. If we then square this, we get that the 47 to the fourth power is congruent to 92. Repeating this, we'll quickly get the 16th, the 32nd and the 64th powers of 47 in a mod 143 world. If I needed to go further, I can see that I have a cycle and that the next squaring will result in 27, 14, 53, 92 and then repeat again. But, this is far enough for this problem. Now I can write my original problem in terms of factors, whose exponents are an integer power of two and then replace those with their reduced values to get my result. To really see how this works for an arbitrary exponent, let's write out all of the squared values along with an additional exponent that either turns them on or off. Now let's collect the controlling exponents into a binary number. The value of this binary integer is 69, our original exponent. So our algorithm is very simple. We start with the base as our factor and at each iteration, square this factor and reduce it by the modulus. Starting with the least significant bit of the exponent, if that bit is a one, we multiply our running product which we initialize to one. This method, not too surprisingly is called square and multiply and it requires just seven iterations in this case, which is the number of bits in 69. Even if we didn't know that we could reduce the original exponent of 6,789 mod 120, it would have only required a total of 13 iterations. There's not a lot to recap in this lesson. Brute force modular exponentiation, is only practical for very small numbers, essentially toy problems. Reducing the base by the modulus and the exponent by the totient of the modulus, can reduce the size of the problem significantly, but not enough when working with even moderate sized problems to make brute force appealing. Exploiting the repeated multiplication nature of exponentiation, reducing the intermediate results by the modulus at each step allows us to work with numbers no larger than the square of the modulus, but is still impractical for moduli of cryptographic interest. However, the square and multiply technique, reduces the complexity of the problem down to the order of the number of bits in the modulus, which brings the problem size down to something that even resource starved embedded chips can perform. Coming up, we'll learn about Euler's totient theorem and how it lets us determine the modular world that the exponent lives within.
