The next thing we're going to look at is how to compute modular large integers. So the first question is how do we represent large integers in a computer? So that's actually fairly straightforward. So imagine we're on a 64 bit machine, what we would do is we would break the number we want to represent, into 32 bit buckets And then, we will basically have these n/32 bit buckets, and together they will represent the number that we want to store on the computer. Now, I should mention that I'm only giving 64 bit registers as an example. In fact, many modern processors have 128 bit registers or more, and you can even do multiplications on them. So normally you would actually use much larger blocks than just 32 bits. The reason, by the way, you want to limit yourself to 32 bits is so that you can multiply two blocks together, and the result will still be less than 64 bits, less than the word size on the machine. So now let's look at particular arithmetic operations and see how long each one takes. So addition and subtraction basically what you would do is that addition would carry or subtraction would borrow and those are basically linear time operations. In other words, if you want to add or subtract two n bit integers the running time is basically linear in n. Multiplication naively will take quadratic time. In fact, this is what's called the high school algorithm. This is what you kind of learned in school, where if you think about this for a minute you'll see that, that algorithm basically is quadratic in the length of the numbers that are being multiplied. So a big surprise in the 1960s was an algorithm due to Karatsuba that actually achieves much better than quadratic time in fact, it achieved a running time of n to the 1.585. And there's actually no point in me showing you how the algorithm actually worked, I'll just mention the main idea What Karatsuba realized, is that in fact when you want to multiply two numbers, you can write them as, you can take the first number x, write it as 2 to the b times x2 plus x1. Where x2 and x1 are roughly the size of the square root of x. Okay, so we can kind of break the number x into the left part of x and the right part of x. And basically, you're writing x as if it was written base 2 to the b. So it's got two digits base 2 to the b. And you do the same thing with, y. You write y base 2 to the b. Again, you would write it as, the sum of the left half plus the right half, And then, normally, if you try to do this multiplication, when you open up the parentheses. You see that, this would require 4 multiplications, right? It would require x2 times y2, x2 times y1, x1 times y2, and x1 times y1. What Karatsuba realized is there's a way to do this multiplication of x by y using only three multiplications of x1 x2 y1 y2. So it's just a big multiplication of x times y only it takes three little multiplications. You can now recursively apply exactly the same procedure to multiplying x2 by y2, and x2 by y1, and so on and so forth. And you would get this recursive algorithm. And if you do the recursive analysis, you will see that basically, you get a running time of n to the 1.585. This number is basically, the 1.585 is basically, log of 3 base 2. Surprisingly, it turns out that Karatsuba isn't even the best multiplication algorithm out there. It turns out that, in fact, you can do multiplication in about n<i>log(n) time.</i> So you can do multiplication in almost linear time. However, this is an extremely asymptotic results. The big O here hides very big constants. And as a result, this algorithm only becomes practical when the numbers are absolutely enormous. And so this algorithm is actually not used very often. But Karatsuba's algorithm is very practical. And in fact, most crypto-libraries implement Karatsuba's algorithm for multiplication. However, for simplicity here, I'm just gonna ignore Karatsuba's algorithm, and just for simplicity, I'm gonna assume that multiplication runs in quadratic time. But in your mind, you should always be thinking all multiplication really is a little bit faster than quadratic. And then the next question after multiplication is what about division with remainder and it turns out that's also a quadratic time algorithm. So the main operation that remains, and one that we've used many times so far, and I've never, actually never, ever told you how to actually compute it, is this question of exponentiation. So let's solve this exponentiation problem a bit more abstractly. So imagine we have a finite cyclic group G. All this means is that this group is generated from the powers of some generator little g. So for example think of this group as simply ZP<i>, and think of little g as some generator of</i> big G. The reason I'm sitting in this way, is I'm, I want you to start getting used to this abstraction where we deal with a generic group G and ZP really is just one example of such a group. But, in fact, there are many other examples of finite cyclic groups. And again I want to emphasis basically that group G, all it is, it's simply this powers of this generator up to the order of the group. I'll write it as G to the Q. So our goal now is given this element g, and some exponent x, our goal is to compute the value of g to the x. Now normally what you would say is, you would think well, you know, if x is equal to 3 then I'm gonna compute you know, g cubed. Well, there's really nothing to do. All I do is I just do g times g times g and I get g cubed, which is what I wanted. So that's actually pretty easy. But in fact, that's not the case that we're interested in. In our case, our exponents are gonna be enormous. And so if you try, you know, think of like a 500-bit number and so if you try to compute g to the power of a 500-bit number simply by multiplying g by g by g by g this is gonna take quite a while. In fact it will take exponential time which is not something that we want to do. So the question is whether even though x is enormous, can we still compute g to the x relatively fast and the answer is yes and the algorithm that does that is called a repeated squaring algorithm. And so let me show you how repeated squaring works. So let's take as an example, 53. Naively you would have to do 53 multiplications of g by g by g by g until you get to g by the 53 but I want to show you how you can do it very quickly. So what we'll do is we'll write 53 in binary. So here this is the binary representation of 53. And all that means is, you notice this one corresponds to 32, this one corresponds to 16, this one corresponds to 4, and this one corresponds to 1. So really 53 is 32 plus 16 plus 4 plus 1. But what that means is that g to the power of 53 is g to the power of 32+16+4+1. And we can break that up, using again, the rules of exponentiation. We can break that up as g to the 32 times g to the 16 times g to the 4 times g to the 1, Now that should start giving you an idea for how to compute g to the 53 very quickly. What we'll do is, simply, we'll take g and we'll start squaring it. So what square wants, g wants to get g squared. We square it again to get g to the 4, turn g to the 8. Turn g to the 16, g to the 32. So we've computed all these squares of g. And now, what we're gonna do is we're simply gonna multiply the appropriate powers to give us the g to the 53. So this is g to the one times g to the 4 times g to the 16 times g to the 32, is basically gonna give us the value that we want, which is g to the 53. So here you see that all we had to do was just compute, let's see, we had to do one, two, three, four, five squaring, plus four more multiplications so with 9 multiplications we computed g to the 53. Okay so that's pretty interesting. And it turns out this is a general phenomena that allows us to raise g to very, very high powers and do it very quickly. So let me show you the algorithm, as I said this is called the repeated squaring algorithm. So the input to the algorithm is the element g and the exponent x. And the output is g to the x. So what we're gonna do is we're gonna write x in binary notation. So let's say that x has n bits. And this is the actual bit representation of x as a binary number. And then what we'll do is the following. We'll have these two registers. y is gonna be a register that's constantly squared. And then z is gonna be an accumulator that multiplies in the appropriate powers of g as needed. So all we do is the following we loop through the bits of x starting from the least significant bits, And then we do the following: in every iteration we're simply gonna square y. Okay, so y just keeps on squaring at every iteration. And then whenever the corresponding bit of the exponent x happens to be one, we simply accumulate the current value of y into this accumulator z and then at the end, we simply output z. That's it. That's the whole algorithm, and that's the repeated squaring algorithm. So, let's see an example with G to the 53. So, you can see the two columns. y is one column, as it evolves through the iterations, and z is another column, again as it evolves through the iterations. So, y is not very interesting. Basically, all that happens to y is that at every iteration, it simply gets squared. And so it just walks through the powers of two and the exponents and that's it. z is the more interesting register where what it does is it accumulates the appropriate powers of g whenever the corresponding bit to the exponent is one. So for example the first bit of the exponent is one, therefore, the, at the end of the first iteration the value of z is simply equal to g. The second bit of the exponent is zero so the value of z doesn't change after the second iteration. And at the end of the third iteration well the third bit of the exponent is one so we accumulate g to the fourth into z. The next bit of the exponent is zero so z doesn't change. The next bit of the exponent is one and so now we're supposed to accumulate the previous value of y into the accumulator z so let me ask you so what's gonna be the value of z? Well, we simply accumulate g to the 16 into z and so we simply compute the sum of 16 and 5 we get g to the 21. Finally, the last bit is also set to one so we accumulate it into z, we do 32 plus 21 and we get the finally output g to the 53. Okay, so this gives you an idea of how this repeated squaring algorithm works. It's is quite an interesting algorithm and it allows us to compute enormous powers of g very, very, very quickly. So the number of iterations here, essentially, would be log base 2 of x. Okay. You notice the number of iterations simply depends on the number of digits of x, which is basically the log base 2 of x. So even if x is a 500 bit number in 500 multiplication, well, 500 iterations, really 1,000 multiplications because we have to square and we have to accumulate. So in 1,000 multiplications we'll be able to raise g to the power of a 500 bit exponent. Okay so now we can summarize kind of the running times so suppose we have an N bit modulus capital N as we said addition and subtraction in ZN takes linear time. Multiplication of just, you know, as I said, Karatsuba's actually makes this more efficient, but for simplicity we'll just say that it takes quadratic time. And then exponentiation, as I said, basically takes log of x iterations, and at each iteration we basically do two multiplications. So it's O(log (x)) times the time to multiply. And let's say that the time to multiply is quadratic. So the running time would be, really, N squared log x. And since x is always gonna be less than N, by Fermat's theorem there's no point in raising g to a power that's larger than the modulus. So x is gonna be less than N. Let's suppose that x is also an N-bit integer, then, really exponentiation is a cubic-time algorithm. Okay so that's what I wanted you to remember, that exponentiation is actually a relatively slow. These days, it actually takes a few microseconds on a modern computer. But still, microseconds for a, for a, say a four gigahertz processor is quite a bit of work. And so just keep in mind that all the exponentiation operations we talked about. For example, for determining if a number is a quadratic residue or not, All those, all those exponentiations basically take cubic time. Okay, so that completes our discussion of arithmetic algorithms, and then in the next segment we'll start talking about hard problems, modulo, primes and composites.
