[SOUND] In this lecture we're going to begin our treatment of number theory. Now you might actually be surprised that until this point in the class we haven't had to rely on or to learn any number theory. And the reason you might find that surprising is because my impression is that when people think about cryptography popularly, the first thing that comes to their mind is exactly the number theory. That's kind of the quote, un-quote sexy part of cryptography. However as we've seen in this class so far number theory is not really needed for a lot of important cryptographic applications. And in particular, all of practical private key cryptography is based on things like stream ciphers, block ciphers, and hash functions, that can be constructed analyzed, and reasoned about, without any mention of any number theory. And so I think the point here is that number theory, is, of course, going to be needed, for public key cryptography, but it's not needed for all of cryptography. There's a lot of interesting things you can do without any number theory at all. Having said that of course, it turns out that some kind of number theory does seem to be inherent for any sort of public cryptography. Now we haven't talked about public-key world cryptography yet. We won't talk about it until next week, but this is just sort of a primer for what we're going to need in that setting. The point of this week is to really cover the basics of number theory, very quickly. That is, the goal here is not to give a survey of number theory. It's certainly not to give a comprehensive course on number theory. But only to present the bare minimum that we need for the applications that we're going to study. And for that reason I'm not going to focus particularly on the proofs of a lot of un-underlying concepts and results unless I think that the proof sheds some insight on understanding what's going on. For those that were interested I can recommend several textbooks that can be used to supplement the material and in particular a lot of what we cover here with appropriate proofs. And also some additional details is available in the Cat Lyndel text book. What we're going to talk about in this lecture is algorithmic number theory. And this is actually interesting because very often from a mathematical point of view or from a mathematician's point of view I should say, they're interested in the existence of numbers with certain properties, or in proving that some number has a particular property. But there are very often less interested in the algorithmic efficiency of determining whether or not some number has a given property. In our setting, the computer scientist setting where we're going to ultimately be interested in implementing cryptography. We do have to also take care to think about the algorithmic complexity of determining various properties of numbers, and of computing various interesting things about those numbers. And ultimately, if you're interested in particular in implementing very fast cryptography, a good understanding of these kind of algorithmic considerations is very important. Now one thing that's important to stress, is that when we talk about the efficiency of number theoretic operations, we're always going to be interested in asymptotic complexity, of course. But the asymptotic complexity will be measured in terms of the length of the input. That's always true throughout computer science but it's important to stress it here because it's very often easy to get confused between the magnitude of an input and it's length. And in particular if we have some input integer A then the magnitude of A is itself. If A is equal to 1000 then the magnitude of A is 1000. But the length of that input, the length of A, is the length of the binary representation of A. And I'm going to denote that by these two vertical bars surrounding the integers. So, it's sort of like an extended absolute value sign. So we have these the length of A. The binary representation of a, and the binary representation of an integer is the log of the magnitude of the integer. Right, the number of bits that you need in order to represent some number, is the logarithm of that number's magnitude, and conversely, the magnitude of a number is exponential in its length. And again it's very easy to get these concepts confused when thinking about algorithms but we're going to try very carefully to keep them separate. Now in terms of our study of algorithmic number theory, we're not going to dwell extensively on different algorithms for different computational problems. There's a lot of interesting things to be done there, and as I said it is very important when it comes to efficient implementation of cryptography. But for our purposes what we only want to do, is to be able to distinguish between problems that are easy and problems that are hard. Where for us, easy means that it can be solved in polynomial time. And hard, at least for now, is going to mean that it can't be solved in polynomial time. And so beyond making that kind of a very gross distinction we're not going to be extremely interested in fine tuning the, algorithms that we give or that we discuss, or, the problems we consider. And again, there are several textbooks you can use to supplement the material. Several references you can use if you're ever implementing cryptography and want to find out about the most efficient algorithms for some problem. Before I jump in, I want to just review some notation, regarding modular arithmetic, some of which is a bit idiosyncratic. By a bracket a mod N, I'm going to mean the remainder of the integer a when divided by the integer N. So this means you just take, a divided by N. You compute some quotient, which here we don't care about. And you take the remainder. And note, of course, that bracket A mod N, has to lie strictly between 0 and N minus 1. I want to contrast that with the more standard notation that you might be familiar with, namely that A ie equal to B mod N. So A being equal to B mod N means exactly that A and B have the same remainder modulo N. But, the point is that the notation on the left, A equals B mod N, is different from the notation a mod N inside the brackets. Because again, A equals B mod N is expressing something about the relationship between two integers. And A mod N inside the brackets refers to a specific integer in the range of 0 to N minus1, which is the remainder of A when divided by N. Okay. [SOUND] So let's jump in with a our discussion of algori, algorithmic number theory by just briefly noting some basic facts about what can be done efficiently. So if we look at different standard arithmetic operations, we can see that their's actually can be done efficiently. So integer addition for example, can be done efficiently using the standard grade school algorithm. And if you think about how that works, you'll see that it runs in time, essentially linear, in the length of the inputs and the same for subtraction. Multiplication can also be done using a grade school algorithm. The running time now is quadratic rather than liner. And I'll mention that better algorithms are known, but, again, for our purposes, we're just going to be happy with the grade school algorithm because it does run in polynomial time. A little bit more difficult to see, but perhaps not very surprising, is that division with remainder, can be done efficiently. And this in particular means that we can compute bracket A mod N efficiently by just performing the divisions and taking the remainder. For that reason similarly, we can do modular addition, subtraction, multiplication, and reduction efficiently as well. So for example, modular multiplication, would just mean that we have two integers. We want to compute their product, modulus if any N, modulus N if any. [COUGH] And what we can do there is to simply perform the multiplication over the integers and then reduce mod N. And because of those component operations can be done efficiently we know that the entire computation can be done efficiently. What about a more complicated operation, in particular, modular exponentiation? And I focus here on modular exponentiation really for two reasons. First is that it's an important computation that's going to be used all the time in cryptography, and second, because I think it gives a very good illustration of a non trivial algorithm. That is one where the naive algorithm as we'll see does not run in polynomial time, but with a little bit of cleverness you can come up with an algorithm that does run in polynomial time. So lets look at the problem of exponentiation. First of all think about exponentiation over the integers. So here's there's no modular reduction. Let's say we want to compute A to the B, all right, the integer A to the Bth power. Well, let's first consider the size of the result. So the number of bits that we need to specify the result, A to the B, is going to be the order of the logarithm of that, which is the order of the magnitude of B, times the length of A. And what you can see, here, is just writing down the answer can require exponential time, exponential in B, that is. Because the running time, sorry the, the number of bits we need to specify the answer, is going to be linear in the magnitude of B, rather than length of B. So we don't really have any hope of computing integer exponentiation in polynomial time. Fortunately in cryptography we never need to compute integer exponentiation, what we do need instead is modular exponentiation, where we're interested in computing the result of A to the B modulo sum, given modulus N. And note here we don't run into the problem we had before, because the size of the answer here is going to have to be at most the size of N, because the answer has to lie in the interval 0 to N minus 1. So how do we do it? Well the first thing to observe is that a strategy that will not work. If the compute a to the b over the integers. And then reduce the result mod N. That won't work because as we just noted, the the length of the intermediate result, A to the B over the integers cannot even be written down in polynomial space. So, that's not the approach we're going to want to use. Let's consider a, maybe a naive algorithm that we would want to use for computing modular exponentiation. So here, I'm just writing a simple function that takes three arguments, A, B, and N and is meant to compute the result, A to the B, mod N. And we'll assume that B is greater than or equal to 0. We won't worry about negative exponents, for now. They can be handled but it's not important for our purposes. So one natural approach is to just start off with a variable called ans that's going to hold the answer, initialize that to 1. And then for I ranging from 1 to B, what we'll do is we'll simply multiply the current value of the answer by A and then reduce mod N. So this of course is not valid C code. This is meant to just be pseudo code. But what I've indicated here is that we just multiply a into the current answer and then increment B. And we're going to avoid the problem that we had on the previous slide. Of first computing A to the B and then reducing modular N. Because you'll notice here that we're reducing modular N at every step. So every time we multiply, we're going to then reduce. And so the value of Ns at any point during the computation, is going to be strictly in the range of 0 to N minus 1. So we do this for a total of B iterations of the loop, and then we return the answer. This will indeed give the right result, but what's the running time of the algorithm? Well, it's easy to see here that the inner loop is going to be running for a total of B times. And that is not, efficient. That is not polynomial time. Because we would like an algorithm that runs in time polynomial in the length of B not in the magnitude of B. And again here we have a loop running for a number of steps linear in the magnitude of B, so this is not going to qualify as an efficient algorithm. What kind of approach could we use to get a more efficient algorithm, to get in particular a polynomial kind of algorithm? Well it's easiest to think about the problem if we assume for simplicity that B is a power of 2. So let's say that B equals 2 to the K for some integer K. If you kind of unwrap the proceeding algorithm or maybe just view it in a different way. You can see that the preceding algorithm roughly corresponds to performing B multiplications of A. That is, to computing A times A, times A again, times A again, et cetera, for A total of 2 to the K minus 1 multiplications. But a better way to do the computation. Would be to first square A, right to just compute A times A, take that result and square it again. Take that and square that, and keep going until you've done a total of K squarings. Or K minus 1 squarings I guess. So, that would give a much better algorithm. Then the former one because we have k squarings versus two to the k minus one multiplications. And again, the important thing to note here is that k is order of log of B, which means that K is order of the length of B. So what we have here in the second case is an algorithm that's running in time linear, in the length of B. So of course this only works when B is a power of two. But as we'll see in the next slide we can modify this approach even when B is not a power of 2. So here is the algorithm. So again we're going to have an algorithm taking as input A, B, and N. And we're going to again assume that B is greater than or equal to 0. What we'll do here is to initialize two variables. One called X and one called T. We'll initialize X to a and T to 1. And then while B is greater than 0 we do the following. So first of all we check if B is odd. If B is odd we then compute a within a set T equal to T times X mod N. And we reduce B by 1. Then we compute X equals X squared And B is equal to B divided by 2. So note that in this point the algorithm must be even because if it were odd at the beginning of the loop then in the previous step we checked that it was odd and so we subtracted 1. We keep doing this as long as B is greater than 0, and then finally return t. Now it's a bit difficult, perhaps, to be convinced that this is working. But you can prove that the algorithm works by looking at, or by showing that the algorithm satisfies the following invariant. And the invariant is, that the answer, the correct answer that you're looking for is always equal to T times X to the B amount N. And that's certainly true at the beginning of the algorithm when we initialized the variables because then X is equal to A and T is equal to 1. And indeed A to the B amount N is exactly the answer we're looking for. And then you can check throughout the loop. That if B is even for example, then what we end up doing is squaring the value of X and reducing B in half. And so X to the b mod N, or t times x to the b mod N, is of course equal to T to the X squared, to the B over 2 mod N. Just algebra. And similarly, if B is odd, we then shift a factor of X into T, and reduce B by 1. And you can write down on paper and easily verify that the invariant is satisfied. At the end of the algorithm, B is equal to 0, and so the correct answer is given by exactly T. And T is a value that we return. What's the running time here? Well the important thing to note is that in every execution of the inner loop. The value of B is decreased by at least half. And that means that the number of iterations of the inner loop is going to be 0 of log B, which is linear in the length of B. In each iteration of the inner loop, we perform some computation that can be done in time polynomial, in, A, B and N. And so without getting into too much of a fine grained analysis we can see that the overall running time of the algorithm is indeed polynomial in the length of it's three inputs. In the next lecture we'll spend some more time on modular arithmetic. And we'll also introduce the very important notion of an abstract group that will allow us to think in a more clean away about various of the manipulations that we're going to be doing and that we're going to use for crypt, for cryptography. See you next time.
