[SOUND]. We'll continue our discussion of number theory by introducing the notion of a group. This is actually a very fundamental and important notion both for mathematics in general, as well as for applications to cryptography. Roughly speaking the notion of a group provides a way of reasoning about different objects, that share the same underlying mathematical structure. And hopefully this will be, become more clear when we see the definition, and then see a couple of examples. Now one thing I will say, is that an understanding of groups, and a little rudimentary group theory, is strictly speaking, not necessary to understand crypto or cryptographic applications. But in my opinion, just a little bit of knowledge about the concept of a group. Does make things conceptually easier, it puts things in an appropriate framework, and I think makes it easier to grasp, what's really going on under the hood. And since that's part of what you're interested in learning from this class, I do think it's important to spend some time on basic group theory. So let's jump in and look at the definition. We're only going to be interested here in abelian groups and so that's what I'm going to define. So an abelian group is a set G, a set of elements, along with a binary operation that for this slide we're going to denote by this little circle, defined on the elements of G. This means that for every two elements of G you can compute a circle b, and then get back as a result some other element of the same set. And this has to satisfy certain conditions. And the conditions are the following, so first of all, we require that there exists some element in G that acts as an identity. And, on this slide, we'll denote that element by e. And the property of this element e, the fact that it acts as a, as an identity, means that e.g is equal to g for every element in the set G. We're also going to require that every element in g, has an inverse, h say, such that h.g is equal to this identity element. We require also the notion of associativity which should be familiar to you from basic arithmetic and this just requires that for every three elements f, g and h in the set G. If we first compute g.h, and then compute f dot the result, then that gives the same answer as if we first compute f.g, and then take that intermediate result and take that dot h. So it doesn't matter, in some sense, what order we do the operations. We're only going to consider as I mentioned earlier abelian groups. And abelian groups have the extra property that for all g and h, in the set G, g.h is the same as h.g. And one more piece of notation, the order of a finite group g, and we're only ever going to consider finite groups in this course. The order of a group g is the number of elements in the set G. So let's look at a a piece of notation. So just to simplify matters rather than writing this little circle to represent the group operation. It's very common to, instead, use either additive notation, or multiplicative notation, to denote the group operation. So under additive notation we write g plus h to denote the group operation on g and h, and under multiplicative notation we write either gh or g with a little dot instead of a little circle h. Analogous to the way you would write multiplication of integers in grade school arithmetic. Now it's important to keep in mind that just because we're writing things in this way, does not mean that the group operation, corresponds to integer addition or multiplication. For the most part, in all the examples we talk about in this class ultimately things are going to be based on integer addition or multiplication, though they will not be identical, to integer addition or multiplication. But it's also very easy to consider examples where addition and multiplication of integers is nowhere to be seen, and you define the group operation completely abstractly. But you nevertheless, might write it, using this additive or multiplicative notation. Just a few more pieces of notation to represent the identity element, it's convenient to use, 0 or 1. 0 in the case of additive notation, and a 1 in the case of multiplicative notation. This is again, just something a more convenient way to represent the identity, rather than using e. The inverse of an element, is denoted in the natural way by minus g, if we're using additive notation, or g to the minus 1 power, if we're using multiplicative notation. And when we talk about grouda, group exponentiation, which means repeated application of the group operation, we denote that by m.a when we're using additive notation, which again refers to repeated addition, in quotes, of a to itself a total of m times. Or when using multiplicative notation, we write a to the m, to refer to repeated multiplication of a by itself m times. Where again, we're careful to understand that this does not mean that we're, that we're referring to integer multiplication or integer addition in either case. One thing I'll point out here, I, this starts getting a little bit abstract, but I think it's, if you can understand this, you have a good understanding what's going on. When we write something like m.a using additive notation for the group, a is a group element, and m is an integer. So what we're talking about here is not the group operation, applied to m and a. Right? M is not even necessarily in the group, it's type is that of an integer. But we're, what we're referring to is repeated application of the group operation to the group element a, a total of m times. And here we're assuming that m is a positive integer you can handle negatives and zeros in really pretty much the natural way. And we don't handle fractional m at all. In terms of performing computations in groups, so we're again going to ultimately be interested in the algorithmic efficiency of performing different operations and different computations in the groups that we're going to be working with. And we're always going to implicitly assume that for any groups we're talking about, in the context of cryptography, that it is possible to efficiently recognize, what a group element is. So that is, we're ultimately going to be writing every element of some group as a sequence of bits. And it should be possible, given some sequence of bits, to tell whether or not that represents a valid group element. We also are going to assume that the group operation can be computed efficiently. So again this means that given two group elements, represented by their bit strings, we can compute the group operation on those two group elements, i.e those two strings. And further more that we can compute this group operation in time, polynomial in the length of those strings. Now when I say assume here, I don't mean that we don't think about it all. What I mean is that we, of course, have to analyze for some group of cryptographic interest, that it is indeed possible to perform these operations efficiently. But we will assume that somebody else has done the work for us, and therefore that they can indeed be done efficiently. Now the fact that the group operation can be completed efficiently, means also that group exponentiation can be computed efficiently. And this follows using the same algorithm that we showed last time for performing modular exponentiation, and the connection between the two might become more clear after we show that, in fact, some form of multiplication modulo N can indeed be viewed as a group operation. Let's see an example of a group, this is perhaps the most basic example. So consider the set ZN, which denotes the set of elements from 0 to N minus 1 under addition modulo N. So this means that the group operation here or the operation, is defined as taking any two elements in the set, adding them and taking their result reducing it modulo N to give back an integer in the range 0 to N minus 1. Well it's not too difficult to convince yourself that this does give a valid group, the identity element here is simply 0 which is in the set. The inverse of the element a, is the element minus a reduce modulo N, where we need to reduce modulo N so that we get back something in the same set. Associativity and commutativity of the group operation is immediate, it follows from associativity and commutativity of the underline operation on the integers. And the order of this group is N, because it contains exactly the N elements, the N integers from 0 to N minus 1. And the exponentiation here m.a corresponds to as we said earlier repeated addition of a to itself m times. And as we noted this can be computed efficiently in fact in this case you can compute just by using standard integer arithmetic. This is kind of a coincidence if you want to call it that, due to the fact that the element a here can be viewed both as an element of the set ZN, as well as an integer. Now what happens if we try to extend the previous example and think about multiplication modulo N? Well, the first thing to note is that the same set 0 to N minus1 is not going to be a group under this operation. One would have to be the identity, but for example, the element 0 has no interest, there's nothing, no element in that set when multiplied by 0, is going to give us 1. In fact, even if we exclude 0 from consideration, if we take it out of the set, that doesn't solve the problem because for example, think about the case when N equals 4. While there's no inverse of 2 modulo 4, something that you can check just by brute force and numberating over all the possibilities, right? The set in this case would be the elements 1, 2, and 3 under multiplication modulo 4. And none of 1, or 2, or 3, multiplied by 2 gives 1 when reduced modulo 4. So what we need to do instead is to restrict the elements in our set. So let's first begin with a definition. Say that the element b is invertible modulo N, if there is some other element, b inverse, such as b times b inverse is equal to 1 mod N. In other words we're just defining invertibility modulo N to mean that b ahs an inverse modulo N. And if such a b inverse exists it turns out you can show that it 's unique modulo N. So an element, if it has an inverse has exactly 1 inverse. I'll note also that we can use this to define a notion of division by b. So when we're mark, when we're working with an operation of multiplication modulo N and we say or we talk about division by b in fact what we mean formally is multiplication by b inverse modulo N. And in fact, the notion of division is not really well defined modulo N if the element b does not have an inverse. So the operation of division by b really should only be defined when b is invertible modulo N in the first place. Now the natural question is, which elements are invertible? And we can fully characterize those elements by the following theorem. Element b is invertible modulo N, if and only if the greatest common divisor of b and N, is equal to 1. We're not going to prove that here, although a proof is not incredibly difficult, but it's not really so important for our purposes. And this also means, not only can we characterize invertibility, but we can efficiently test wether a given element is invertible, and this is a consequence of the fact that gcd can be computed in polynomial time, that is, given two integers, being n here, for example, we can compute our greatest common divisor, in polynomial time. This is not trivial, but it is something that has been known since the time of Euclid. The algorithm for doing this, actually, is called the Euclidian algorithm. Now coming back to the question of invertibility. So what we said early, than an element b is invertible if the greatest common divisor of b and N is one. So if we take for example p prime, for considering a prime modulus, then all of the elements between 1 and p minus 1 will invertible modulo p. And that follows from the fact that the greatest common divisor of p, and any integer, less than p, is going to have to be 1, right? Because the only factors of p are 1 and p. Nothing else no, no integer smaller than p can have any other factor than 1 in common with p. A second interesting example is given by a moduli of the form, a product of two primes. So say N is equal to pq, for p and q distinct primes. Then the invertible elements, modulo N, are going to be the integers from 0 to N minus 1, that do not share a factor in common with N other than 1, right? This is just sho, it's just they're re-expressing the fact that the greatest common divisor of the element, and N should be 1. So this means, that we can imagine listing out the elements from 1 to N minus 1 and excluding all the multiples of p, and all the multiples of q. And again, this will, what we're left with is going to consist of exactly the elements whose greatest common divisor with N is equal to 1, and this is a consequence of the fact that that p and q are prime. So it turns out that if we do this, then the set ZN star, which we will define as the set of inverter elements between 1 and N minus 1, is indeed a group under multiplication modulo N. So we came to the question earlier or we, or we noted it earlier, that just looking at multiplication modulo N, does not straight away give us a group, because some, some elements are not invertable. But if we simply take out, if we simply exclude those elements that are not invertible, then what we're left with is a group, and we'll denote that group by ZN star. It's not immediately obvious here that it's a group, because in particular it's not immediately obvious that we have closure, that it is not immediately obvious that if I take two elements a and b, both of which are invertible, then their product ab mod N is also invertible. Never the less this can be shown and, it does in fact hold. The identity is obviously going to be 1. The inverse of a is going to be a inverse mod N. This is where we use the fact that we're restricting attention to invertible elements only. And a before, for the case of ZN, the additive group modulo N, associativity and commutativity here are obvious, because they follow from the same properties over the integers. And, again the exponentiation, that is a to the m, a mod N repeated multiplications of a, m times. And taking the result, modulo N can be computed efficiently as well and this follows from the fact that multiplication can be done efficiently and follows from the exponentiation algorithm we saw in the previous lecture. What's the order of these different groups? Well we'll define phi of N, where phi is a greek letter. To exactly be the number of invertible elements, modulo N. That is, it's the, the set of elements between 1 and N minus 1 whose GCD with N, is equal to 1. And this is precisely the order of ZN star, because we defined ZN star to consist precisely of those elements whose GCD with N is equal to 1. When N is prime we said earlier that every element between 1 and N minus 1 is in ZN star. And so when N is prime phi of N is equal to N minus 1, that is the size or the order of the group ZN star, when N is prime is exactly N minus 1. Furthermore, when N is a product of two distinct primes, then we can compute phi of N using the characterization of the elements of ZN star that we talked about a moment ago. So remember, that ZN star, consists of those elements that we get if we write out the integers from 1 to N minus 1, and then exclude all multiples of p and all multiples of q. So this means, we start with a list of N minus 1 elements. Right, all of the elements from z, from 1 to N minus 1. And then we exclude all the elements of p. Well how many sorry all the multiples of p. Well how many multiples of p are there? Well, we have p, we have 2p, we have 3p, 4p, 5p all the way up to q minus 1 times p. Qp is already too large, qp is equal to N and that's beyond the limit of our set. So if we cross out every multiple of p, there will be exactly q minus 1 elements that we cross out. Similarly if we cross out every multiple of q, we end up crossing out precisely p minus 1 elements. And note here that no element in the range of 1 to N minus 1 can be both a multiple of p and a multiple of q, there is no double counting going on here. Because again, p times q is equal to N, which is beyond the range of our set. So the total number of elements in ZN star, is given by our list, N minus 1, minus the q minus 1 elements we cross out because they're multiples of p, minus the p minus 1 elements we cross out for being multiples of q. And that simplifies to the very nice form p minus 1 times q minus 1. So the upshot is that phi of N when N is a product of two distinct primes, i.e the size of ZN star when N is a product of two distinct primes, is exactly p minus 1 times q minus 1. Okay, so let's go back now to our discussion of abstract group theory. A very important theorem of group theory is called Fermat's little theorem. And it says the following, let G be a finite group of order m. That is, having m elements. Then for any element, in that group, and element G in that group, it holds that g to the m, is equal to the identity. Okay? So, here, we're writing the group, multiplicatively and what the theorem says is that, if m is the order of the group, then if we repeatedly apply the group operation to g, m times, then we get the identity element. The proof is omitted, it's again not something that's very complicated, but it's not very important for our setting, either. Just an an example to illustrate the theorem, if we take the group ZN, the group of elements under addition modulo N, then we said earlier that this group has order N, and therefore what the theorem tells us is that for any element a, in that group, we have that N times a is equal to 0 mod N. This, of course, agrees with our expectation because of course, N times a is going to have to be 0 mod N because Na is divisible by N. But very, be very careful here, note that, as we talked about earlier a here is a group element, and N is an integer, not an element of the group. In particular, the integer N, is not an element of ZN, because ZN contains only the elements from 0 to N minus 1. Anyway, what we're saying here just matches our expectation, but it does fulfill, or it does illustrate an application of the theorem. Another example, if we look at the group ZN star, where this is the group of, invertible elements, modulo N, taken under multiplication modulo N. So what the theorem tells us here, is that for all a, in ZN star, we have that a to the phi of N, is equal to 1 mod N. Right, that is, that if we raise a to the phi of N power or equivalently apply the group operation which is just multiplication, phi of N times to any element a, then we get the identity element in ZN star, which is of course 1. In particular if N is prime, then for all elements a, and ZN star, which is all a between 1 and N minus 1 inclusive, we have a to the N minus 1 is equal to 1 modular N. A Corollary fromage theorem is that if we let G be a finite group of order m, then for any element g, and any integer x. We can always reduce in the exponent, that is, g to the x, is equal to g to the x reduced modulo m. And the proof is one line. So let's write the integer x, as q times m plus r. This is just division with remainder, we divide x by m, we get a quotient q and a remainder r. Well then it holds that g to the x is certainly equal to g to the qm plus r. We can just re-express that as g to the m, to the q times g to the r, but now Fermat's little theorem tells us that g to the m is equal to 1, so this expression simplifies to g to the r and of course r, the remainder of x divided by m, is exactly what bracket x mod m means. And this is very interesting because it means it gives us something that can be used to speed up exponentiation. In particular if we want to compute g to the x in some group, then what we can do is we can always first reduce the exponent x modulo the order of the group. So just to take a, kind of a silly example. If we were computing g to a 1005, in some group of order 10, then rather than computing the exponentiation of g to the 1005, which would require, you know, some number of repeated squarings and multiplications, if we use the exponentiation algorithm, we, I talked about last time. Well what we can do instead is simply reduce the exponent 1,005, modulo the order of the group, that is 10, and get the result 5. And we only then have to compute g to the fifth power. Which is going to be in general much, much simpler. Another corollary is the following, and this corollary is actually both very important but a little bit hard to parse. So I want to walk through it, let's let G be a finite order m. And then for any integer e, I wanted to find the function, f sub e. F sub e is going to be a function on the group, and the function f sub e, is going to take as input, a group element g, and return the group element g to the eth power. Okay, so we're defining a function on the group itself that takes an input and raises it to the eth power. The claim is that if the GCD of e and m is equal to 1, then this function, f sub e, is in fact a permutation, that means it's going to be a bijection, both one to one and onto. So the function f sub e will simply permute the elements of the group, in some way. Moreover, if we let d be equal to e inverse modulo m, and note that, we know that such a d exists precisely because GCD em equals 1 means that e is invertible modulo N. Well then, the function f sub d, that is, raising to the dth power, is the inverse of the function f sub e. So, again, it takes a bit of time to parse this. But what we're saying is that, number one, f sub e is a permutation, under the stated conditions. And furthermore, that f sub d, will also be a permutation and in particular will be the inverse of f sub e. The proof here is again one line. So once you understand what's going on the proof is rather simple. Okay so it's two lines. So the first part follows from the second, that is, if we can show that fd is the inverse of fe, then that in particular implies that fe is a permutation. So, let's prove that. So we want to show that for any element g, if we apply fe to g, and then apply fd to the result, and we should get back the same element g. Well, fd of fe of g. Is by definition g to the e, which is the result of fe of g, and then we take that and apply fd to that we get, we raise that to the d. So it's just g to the e to the d. Algebraically that's just the same thing, as g raised to the power of the product of e and d, but the previous claim, the one we had on the previous slide tells us, that to compute g to the ed, we can reduce the exponent and modulo the order of the group which is m. So that's equal to g to the ed reduced mod m. But e and d are inverses modulo m. So that means that ed mod m, is exactly 1. And of course g to the 1, is just g. And that completes the proof of the theorem. So it shows you how just a few simple facts, about groups can be used to prove relatively powerful results. In the next lecture, we're going to see how this corollary, leads to a computational problem that in turn is very useful for cryptography. You may have even heard about it that is the RSA problem. As a precursor to that, we'll also talk about the related factoring problem.