Watch Episode
Episode Description
Corey and Jessie go through more of the ZKDL lecture notes. This time diving into Modular Arithmetic, Euler’s Theorem, Chinese Remainder Theorem, and work on some of the Chapter’s exercises if there’s time remaining.
Join in and learn with us!
Transcript
Click to expand transcript
All right, we are live. Waiting for the Instagram stream to go live here in a second. Okay, here we go. Cool. Kicking off episode four of the ZKDL camp. What’s up, Jesse? >> What’s up, man? No intro. It’s kind of It’s like >> strange. Yeah, I’m I’m used to Yeah, I’m used to >> I guess we should make a We can do the hash on that one. I need to upload the video here. Can do that one. >> Okay. >> But uh last time we left off talking about congruence. I think we went through this like lima 3.31 key congruence relation properties. Just start with a congruence class or residues of K. Um, you haven’t seen these before. We’re going through the zero knowledge. Was it distributed labs lecture notes introduction to zero knowledge and we’re in the kind of math overview part of the book um which is you know kind of required math to get to the actual zonowledge part of things. And now we are currently in modular arithmetic. Um, and after this we’ll do I think it’s Oilers’s theorem or no Chinese remainder theorem is next and then Oilers’s theorem. So we’re actually just reading through the book going through examples trying to explain it to ourselves. Um, if you’re watching this, you’re learning with us. You want to go ahead and start reading definition 3.32. kind of wanna because it’s been two weeks since we last did this and I’m I’m not gonna lie like I stopped looking at this because I was working on the pilot installer. >> Yeah. >> So like can you rehash for me what what was the pretext of what we’re about to go into? >> I mean we’re doing modular arithmetic. So like how do you do like what first off what what is what are modular what is what is modular arithmetic? what does it mean to say like five mod 3 and all the different parts of that, what the remainders are >> and stuff like this. Um, and then some of the more mathy stuff on how you can move things around. Um, find what like the con the concept of congruence. >> What is the concept of congruence? >> How you can move from like regular arithmetic to modular arithmetic and back and forth to try and >> do some things. I think the main point of all of this was like we’re finding some good kind of math and shortcuts that once we get to designing circuits or looking at what it means to make a zero knowledge circuit how to then >> make the math work out such that you’re in the end the circuit in has the least amount of operations so that it’s efficient. M okay >> that’s the way I that’s that’s my intuition on what we’re doing here on like why we’re learning about these various math concepts and like how to move and do arithmetic on these things >> that tracks I just reread 3.5 yeah and then like yeah yeah to your point it’s all about optimizing the circuits at the end is all this is for >> yeah and after this is going to be abstract algebra so I think that even goes a little bit deeper >> what about congruence classes Like why? >> I don’t know. We haven’t gotten there yet. >> Okay. Well, that was pre Well, wait, hold on. Oh, we’re on three. >> We didn’t do congruence classes. Just talking about what congruence is. >> This is like I guess like a set like for any given so reading it. The congruence class are residues >> of k modulo n. So if you say like this module n is defined as the set it’s a set uh k + n of z or n * z which is >> integers. Yep. Yep. Yep. >> Is equal to k plus in t what is that as a divisor of t. >> Oh is that what it is? >> Yeah. >> Okay. sometimes denoted as the set of k or k or the set of k subn. So for example, the congruence classes of the set of zero subn 1 sub 2 modulo 2 are respectively even and odd numbers. >> So both so I guess the sub is the modulo, right? It’s a set of zero sub two as even numbers. I guess that means it’s like these are all of the things that are mod 2 like evenly mod 2 and then or there’s no remainder right? So like I look at that and I if I take a number mod two all of the numbers that have no remainder is that set right so I’m looking at the definition above and k is zero right in like in the first example in 3.14 k is zero so it’s just zero plus and then some uh I guess >> factor >> the n is modulus Right. N is modulo two in the example. So it’s two times and then any integer. >> No, it’s it’s going to be n * 2. >> Two is it? >> Oh, okay. Okay. Okay. Wait, wait. No, no, no, no, no. Look, look at it. It’s n is n is two. No. And then z is is the is the incremental? >> Yeah, I guess so. >> Yeah. Yeah. Yeah. And then the next part in turn the congruence class 3 sub5 modulo 5. Oh why do they have to repeat that? >> I don’t know >> why would you I my understanding based on the example above is when you put in the square brackets three >> that is and then the sub. Yeah. >> Yeah. Well no the subscript is the mod. No, >> that’s what I thought. But why would you have to say modul? >> Exactly. Yeah, it’s sounds redundant. Is the set of numbers that give the remainder three when divided by five. >> Huh. Okay. So then >> easier way to say it. I think that exam like that example like like saying it out that way makes it more intuitive for me. Like set of numbers that give the remainder three when divided by five, right? Hm. But I wonder if that was intentional that modulo 5 after writing uh square brackets 3 sub5. >> I don’t know. >> All right. Definition 3.33. The complete residue system modulo n or residue ring is a a set of integers where every integer is congruent to a unique member of the set modulo n. usually denoted as Z subn is equal to open curly braces 0 one two all the way to N minus one. In more formal literature, the set is often denoted as Z / N * Z is equal to curly brace open curly brace square bracket. Oh yeah. Yeah. So it’s a set of congruence classes I guess is how you would Yeah, read that >> complete residue system modulo in >> residue ring. >> Oh, what was it called? When so when you have like um um >> every integrant to a unique member of the set modulo in >> what did you say? Now remember when you have when you have a specific field and you find a generator that is the exponent of the field to the power of that the like is it the generator that is multiplicatively divisible into that field. >> I don’t know. >> Okay. >> I never spent much time in modular arithmetic. All the math that I >> I didn’t either. I I didn’t either. >> I don’t know like of it. Like I have an intuition on how like mod how it works. >> Yeah. Yeah. >> I don’t have the like experience doing it and playing with it and like neither do the nuances and intricacies of it. >> Yeah. >> Maybe we’ll get there. >> Hopefully. I just want to get to some like hands-on example. That’s >> this episode should be a bunch of hands-on examples. >> Yeah, that’d be nice >> because the end of the chapter they have like, you know, exercises. So like we’ll just try to run through the exercises and figure it out. >> Yeah. Okay. Example 3.15. Z sub5 is a complete residue system modulo 5 and consists of the following elements. Z sub5 is equal to open curly brace 0 1 2 3 4. Sometimes the formula literature defines Z / 5 * Z to be the set of congruence classes modulo 5. Okay. So z / 5 * z is equal to open curly brace. It’s a set of sets like you were saying earlier where the first set is uh 5k and what does the colon mean again? >> Uh parameterized by >> 5k is parameterized by k belonging to the uh set of integers z. And so it looks like the thing that we’re incrementing here is um by the elements within the original residue system. So it’s going to be 5k + n where n is zero and then 5k + 1 5k + 2. Is that how I’m supposed to read that or? >> Yeah, I think so. That’s what it looks like. Like the set is like the first if you look at the set 0 1 2 3 4. >> Yeah. And then the complete residue system it’s 5k plus zero which is just 5k and then the dot dot dot to 5k plus 4 the end of the set. So like sure >> do you have any intuition for what this structure actually is doing for us? >> Okay. Me neither. Okay. The aforementioned see like I’m just going to keep reading and then hopefully something will click. Okay. >> Yeah. >> The aforementioned lemmas and definitions describe the properties of addition, subtraction and multiplication. But what about division? To define the division, if such operation is valid at all, we need to consider the so-called modular multiplicative inverse, which is usually denoted as a to the -1 mod n, similarly to real or rational numbers. Definition 3.34. For a modular multiplicative inverse of an integer a modulo n is such an integer a to1 uh that satisfies a * a1 is congruent to a -1 * a is congrent to 1 mod n. Um example 3.16 let us find the modular multiplicative inverse of a= 3 modulo n is equal to 7. We need to find such a I’m just gonna say a inverse inverse. Yeah. Yeah. I’m just gonna say a inverse because that makes so much more sense to me. >> A inverse that satisfies three times a inverse is congrent to 1 mod 7. >> Normally you would say that as dot >> oh three. Yeah. Yeah. Yeah. Sorry. Yeah. It’s a dot product. Yeah. 3 a inverse is congrent to 1 mod 7. By simple brute force we find that 3.5 is congrent to 1 mod 7. Thus inverse of three uh is equal to five. Huh. I would need to do that out. I don’t know if you if you’re like me, but like when I’m reading, >> I only can focus on reading. It’s >> hard. That none of that really meant anything to me. >> Yeah. Let let us find the modular multiplicative inverse of a= 3 modulo n= 7. >> You want to get on the same mirror board as me? >> Sure. >> Right. Is I right? Yeah. Yeah, that works. >> I’ll send you the link to it real quick. >> Okay. Get rid of this. I’ll set a password later. Just let me know where you put the link. >> It’s in Discord. Okay. Joshua, I don’t know what that is. Sorry, Josh. >> Talking about your knowledge right now. >> Someone on Instagram asked about our impressions or thoughts on Coin Mafia. >> Oh, I don’t know what that is. >> I don’t know what that is. Never heard of it. This ain’t the episode to look into it. This is loading really slow. The mirror board. >> Yeah, >> I don’t mind. Works on my machine. >> Works for me. Oh my god. Load. >> Got too many computers. >> No, it’s probably Maybe I should just open it with Chrome instead. Brave always has like issues. Let’s try to run this example out. There it goes. Yeah. All right. So find modular multiplicative inverse of a = 3 mod n = 7. need to find such that a inverse satisfies three. So a - one 3 a inverse congruent to one on seven. By simple brute force find that 3 * 5 is to one. 3.5 is equal to is cong to one odd seven. What how is 3.5 congruent to one mod 7? It’s like it’s 15 3.5 if I look like figing this out. 3.5 go to one mod 7. So 3 link to work on my tablet. >> Mod 7 gives you one right as a remainder. That’s true. That’s seven here. 15 mod 7 because like seven times two is 14. So you get a remainder of one. So I guess that means 15 mod 7 is congruent to one mod 7 because they both have the remainder one. So I don’t how that >> Did you do the dot product of three and five? I forgot. Yeah, just the 3 * 5 is 15. So like 15 mod 7 gives you a remainder of one. You have that. >> Oh wait, so it’s not it’s not a >> for for for for scalers >> dot product of scalers is just multiplication. >> Yeah. >> Got it. Yeah, that makes sense. So >> the thus means, right? It’s like how do we get to like three inverse equals five? Where did that How does that work? Three times five. Okay. >> What is >> I see. >> So if I look at here, let me change my color my ink. If I look here, right, I’m plugging in just like plugging in, right? So like what number >> I’m playing catchup. Walk me through what you did. >> Now I’m looking just reading the example. The example says by simple brute force we find that 3 * 5 is congruent to one mod 7. >> So I just multiplied out 3 * 5 gives you 15. Took the modular >> took took mod 7 >> and then you got one remaining right. >> Yeah. Yeah. >> So if we So basically it’s saying like if I look here what number what * 3 is going to give me a remainder of one mod 7. So what * 3 mod 7 has a remainder of one. 3 * 5 is equal to 15 >> mod 7 gives you a remainder of one. So by like brute force >> the a inverse >> for this a a= 3 mod n= 7 inverse of a is equal to 5 because it fits into this. So I think by definition you’re always looking for the thing that is one. I the notation is because I get what they’re saying because they’re putting it three three inverse of three is equal to five but like when they write out that statement >> yeah so if I look >> as it stands alone it makes zero sense >> the definition is like look at the definition you’re looking to find the inverse >> is what a times a inverse gives you is congrent to one mod n right? >> Yeah. >> So they give you a and n >> but a is three right? So like for instance >> so what times >> what times three gives you 1 mod 7 answer is five because 5 * 3 is 15. >> You see how you see how the definition is a * a inverse. >> It should be a * b inverse where b is equal to 5 and a is equal to 3. You’re looking you’re one it’s it’s it’s an identity right so it’s like you do this is the identity for modular arithmetic what is the negation >> a * a inverse is going to be one like I get that but but >> one mod whatever whatever modulo we have right because we’re doing it like we’re doing this is modular thing so it’s always going to be >> this is this is all I need let me let you sketch out what I mean on your mirror board on my tablet. There’s my little doodle thing in there. Oh no, it switches. So like if I draw the clock here from used previously. >> No, I have I have more of like a beef with the way that it’s structured. Like for instance definition so like you see what I’m writing here def 3.34 right the definition is uh a time a inverse is congruent to a inverse time a >> is congruent to one mod n. >> Yeah. But in in in the example the example they’re giving you so a= 3 modulo I’ll write it out fine n is equal to 7. So like you said right you just basically a= 3 n is equal to 7. But all I’m saying is like for Okay. And then I’ll I’ll I’ll write it out. So 3 * a inverse is congruent to 1 mod 7. All I’m beefing over is that in this format, sorry. Uh let me undo that. Can I not hit the undo button? There you go. I’m going to use a different color so it really stands out the what I’m talking about. So like essentially they’re taking this, right? That’s this structure right here, right? >> Yeah. >> All I’m beefing over is that the way that I I know that you know a * a inverse is equal to one. That’s the identity. The dotproduct of the identity >> mod one mod whatever the modular is. >> Yeah. Yeah. Yeah. But like what all I’m saying is like in this case like um the answer was uh when they wrote it out they said three three uh inverse of three is equal to five it’s just it it it reads a little bit weird because >> it does >> like because this is this is five. >> That’s five >> but it’s but uh it’s actually not even the inverse. It’s just five. >> That’s just five. Yeah. Yeah. Yeah. >> But >> the inverse of the three is >> like three to the negative like inverse of three modulo 7 is going to be five. >> I don’t know what the right words are to say this right now. >> Yeah. Yeah. Yeah. >> Looks weird. But like you always keep in mind like modular arithmetic. So like like this like the notation doesn’t >> sit well for intuition. >> Right. Right. Right. Because like if if they’re using A’s here, right? It should be three. It should be like it like that. You know what I mean? >> Which doesn’t make any That doesn’t help. >> Which doesn’t make sense. Exactly. It doesn’t help. That’s what I’m saying. Like, as I’m saying, it doesn’t help. >> I was trying to look for something. >> That’s why I was asking like this. They should have made this B or something, you know? >> Yeah. >> I I I mean, I get like 15 mod 7 is going to be, you know, you go around the clock twice and then you have one left over. Like, I get that. I’m not I’m just beefing over the notation that they’re using because it’s I don’t know just I would have used not a time a inverse. I would have used a time b inverse but that like you like you’re saying it’s not the identity matrix. So it’s just there’s something weird here with the notation that doesn’t make sense to me but I get what they’re trying to do. >> Yeah, the intuition of inverse in mod in modular systems isn’t straightforward. I mean also writing it like that that expression is is is false like three three in like inverse of three is equal to five like that that that expression is not an appropriate way of expressing what they’re what they’re trying to say I don’t think is it >> it I would imagine it to be I’d have to look at a different book maybe there’s maybe someone in the audience can tell us bring in one of the GK guys in the m like >> that would be nice. >> Hey Blah, >> like just tell us if we’re or like tell me if I’m to >> tell BJ make us feel stupid about this and make us make us understand it better. >> Okay, cool. We can move on. >> Yep. Um All right. So we got that kind of >> remark the inverse if exists behaves similarly to the usual inverse over rations or reals. For example, um a squar inverse is equal to a inverse squared. Okay, which means we can first find the inverse then square the value or vice versa. So whichever process makes sense, you can do it. >> Um yeah, >> question then is when does the number have the inverse? Consider the following theorem. >> The modular multiplicative inverse a inverse mod n exists and if and only if the greatest common denominator of a and n is one. Okay. Makes sense. >> So if it’s prime then it’s got an inverse. >> If you can do prime factorization to it then >> yeah. >> Okay. So based on the extended you clean algorithm one definite 3.5. >> We build the algorithm that can verify an existence and find the inverse. So here’s the algorithm for doing this. Maybe we can write this out here in a little bit when we get to the exercises. So extended greatest common denominator need that in order to do the inverse. So if you take you’re trying to find the inverse of a and n I’m looking here right trying to find the inverse of a andn you first find the extended greatest common denominator of those two things. If that is not equal to one you raise a value error otherwise you give u which is what we have over there in the previous so it doesn’t exist. never did this out on by hand. >> Yeah. It’s basically saying like if it if if if the greatest coming under isn’t one then it doesn’t exist. >> Yeah. Yeah. >> If it is one then return you. So >> that makes sense. >> And they’re using it looks like one of the previous Yeah. the extended ukarian algorithm here. >> It’d be good to take the things. >> Yeah. Take snippets of the extended uklidian algorithm above as it’s explained and then like slap it into mirror and then take this and then slap this into mirror as well. like just a snippet. >> I imagine we’ll do that in the exercises. >> Okay. >> Why don’t we just get through this and then start trying to power through exercises just how we do it. >> Yeah. Yeah. >> Let us verify manually that 12 in 12 inverse modulo 17 was found correctly. Consider the following example. Let us find the modular multiplicative inverse of a= 12 modulo n= 17. First of all, we need to verify that the inverse exists at all. In other words, whether the greatest common greatest common denominator of 12 and 17 is equal to one. So they go through that algorithm to find that yes, it does exist because the greatest common is one. That’s the that’s the um thing we did last time of the extended ukarian algorithm. >> I bet that’s a really cool visual >> Yeah. >> representation of what the extended ukarian algorithm is, right? >> Yeah. Yeah, >> you can map that to something visual that I think would probably provide some pretty good intuition. >> Yeah, >> if you can see how it progresses down. >> Mhm. >> Um because you can take them like modulo 17 modulo 12 >> gives you a remainder of five. Then you take >> 12 and you modulo two or modulo >> 12als 5 gives you two five modulo two gives you of one and then you’re done. one is the greatest common denominator. >> That’s the way that extended algorithm works. But like I bet there’s a really cool graphic visualization just to make sure that it gets >> like like the bubble sort like visualizations. Have you ever seen those? >> Yeah. And there’s like noises like >> Yeah. Okay. Cool. Heavy existence. Um which means that you can find an inverse. um they’ve previously used bee coions but in this case we’ll show you another method. Let us iteratively go backwards from qu equation three. Focus equation three. This one right here 5 = 2 * 2 + 1. >> Is that the one they’re talking about? Okay. Yeah. >> I don’t know. And then they’re they’re moving one on the other side. So it’s five minus the rest one. Yeah. So they’re just flipping it over. >> Yeah. And then what do they do? >> 1= 5 - 2 * 2 = 5 = 5 - 2. So they just plug the previous step into that part. And so combining we have five times the entity 17 - 12 one. As you can see we have found the basil coefficients. the greatest common denominator of 12 to 17 equal to 5 * 17. It’s a different way of getting to the basil coefficients by working backwards. >> Therefore, the inverse is -7 because like plugging in so u is the baso coefficient. So like uh u is minus7. If you look at the basil coefficient definition like the basil coefficients are five and negative7. >> Mhm. >> And by definition because you do this part like u ends up becoming the inverse of five. Yeah. >> Interesting. Okay. We’ll have to confirm that. Note that the complexity of this algorithm is the same for algorithm one. There you go. That’s you tying it back into bit operations for use from this later when making things. In real applications, typically n is much n is larger than a. So the complexity is simplified to o log squar n. Okay. The multiplicative group of integers modulo n denoted uh z subn of x or to the x is a set of natural numbers that are co-prime to n and less than n. In other words, a within the natural numbers parameterized by the greatest common denominator of a and n equals to one. So only the numbers that are co-prime co-prime to n and less than n. >> Yeah. >> Interesting. Okay. >> So this >> what does that do for us? >> Since all natural natural is less than co-prime to 11 since 11 is prime. >> Mhm. However, for 12, it’s smaller since the integers 2 3 4 6 8 9 10 are not co-prime of 12. >> Yeah, I see. So, this is a shorthand. So, they’re just going to start writing Z subscript >> as a set of co-prime numbers of 11. >> Yeah, they’re just going to use that format. Z multiplicative. I wonder what those are useful for. But that’s I bet that comes into play pretty heavily when doing um optimizations. >> Z, how do you read this? ZX subn. Is that how we’re going to read it? >> Um Z to the X subn. >> I don’t know. How would you say that? uh fundamental object and number theory plays a crucial role in cryptography forming the basis almost of almost or basis for almost every cryptographic primitive the structure of the group Z to the X subn has a crucial meaning and has deep connections with the algebraic or with algebraic structures even the number of elements of Z subn Z to the X subn has a special name which we define below definition 3.37 Oilers’s toion to function uh is that f of n is the cardality of the multiplication group of integers z to the x subn. In other words, f of n is equal to absolute value of z to the x subn. >> Cardinality. So that’s like >> yeah what is cardality? >> Cardality is usually a a like a increasing order. Um, >> okay. >> That’s why it’s absolute value. It’s usually like denotes the like an order of something. It’s like in increased complexity. So like like dimensionality, right, would be kind of like a cardality like a like the the real numbers have cardality three like real real space is like cardality three because it’s r to the third. >> Oh, okay. Okay. I see what you’re Oh, okay. Okay. Okay. I remember this is like in XYZ space cardality 3. >> Yeah. >> Yeah, I got you. I remember it’s coming back. All right. >> Alternative Oilers to function interpretation is the following. VN counts all co-prime integers within in range one to n. Remarkably, VN has a lot of curious properties which we specify below. Let’s see how remarkable this is. Lima oilers to function properties if you have one is one. If you have P is the P minus one where P is prime. Okay that’s interesting. So any prime number the P is one minus the prime number just like you looked at the fee of 11. >> Mhm. >> It was 10. >> Okay. >> Fe of P and Q is Okay. That’s interesting. That makes sense though. I heard in uh there’s a there’s a recent Lex Freriedman um podcast where he interviews a guy who is a specialist in set theory. >> Okay. >> Um really interesting if you like the philosophy of math. >> Yeah. >> Uh can you sum up what that means in a nutshell? Like what is the philosophy of math in a nutshell? like uh for instance like one of the things that he said which I was was which is what I was going to get to is like they consider primes as the atoms of math. >> Okay? >> Right? They’re like the things everything’s built from. >> Okay? >> So like if you think about all of math primes are like the atomic unit of math. Okay? because everything can be co like every like find prime factorization every number can be a decomposition of primes. >> Mhm. It’s just a matter >> of the basis functions of all of math. >> And I thought like if you think about that as a like if like you know the abstract math space and how it relates to >> you know reality. >> Yeah. >> And like but that only that’s only for uh real numbers. It doesn’t consider imaginary numbers. Right. >> No, it does. Imaginary numbers are still numbers. They’re just it’s a it’s a it’s a it’s a two plane. >> You can factor in a you can in fact you can factor a complex number. >> Yeah. >> Into primes. >> Uh I mean it would still have to lie onto the complex plane. So it’ be a factor of primes plus or minus a factor of primes. I times I >> Huh. Okay. It’s like saying like you can’t you can’t factor maybe I’m wrong here but like you can’t factor x and y into a single prime number but you can do x and y into two prime numbers of the coordinate set. >> Yeah. You you’re just you’re just postulating that. You don’t know that for sure, right? >> Yeah. It’s my intuition. >> Okay. Maybe it’s >> there’s not there’s not I don’t think there’s a mapping of the complex plane to just prime numbers. That’s like infinite sets and stuff. So like that’s maybe like beyond what we need to talk about here. Anyway, with these properties, we can derive a general formula for Eer’s to theorem function known as the prime factorization of n. Okay for any number n equal to one alpha 1 >> general formula oilers to function is f of n is equal to the product from i to t p of i to alpha i minus p of i >> what’s the difference let me ask you this like what’s the difference between a lema a corollary you know >> corary is like a different way of saying the same thing the way I’ve always understood the same as a lema or >> a lema is like it follows that. >> Okay. >> Right. >> I don’t know. I always I always like >> the lima here is like here’s like a lima is like given given this definition it follows that these things are true. >> Then what’s a theorem? I’m just going to go through all the stuff that I have the a true statement like like an It’s been proved true. There’s no there’s no proof. There’s a proof. >> There’s no counter but it’s not like you know how like I guess in physics you have like what like laws but laws are not necessarily like some laws are not laws. What was it? How did that go? >> Theory is usually something that has been backed by a tremendous amount of evidence. >> Okay. And it has and it has like >> it is it is a um almost like a mathematical construction that explains some phenomenon that >> is backed by a tremendous amount of >> uh evidence. >> Yeah. from experiment and then has predictive powers that allow you to following the theory that given this given this theory to be true we predict this thing to be happen to happen that say hasn’t been haven’t hasn’t had an experiment yet so you can go out and do new experiments that then validate that theory it’s like I have a hypothesis that based on this theory I can do this thing that hasn’t >> my question is like my question is less about it’s more about the the hierarchical organization of terms in math that par that parallels that. >> Yeah. I don’t know. >> How does that go? >> It’s a good question. >> Like is it theorems then lemmas then corlaries and like it’s like like theorems are the basis of everything like they’re the lawser >> like a theorem in my opinion is like given a given a framework of axioms for something math. So axioms are like these things were just taken to be true. There’s no like there’s no proof of these things. They’re t they’re taken to be true >> and then subject to logic on how we can put these things together using the axioms. >> Yeah. >> We can prove that this statement is now true, right? >> And that’s the theorem. The theorem is like we have proven this statement to be true from the set of axioms. That’s and and logic and pure logic. It feels like corlary is like an alternative explanation of the exact same theorem. >> Okay. >> Um and then limas are like given this theory to be true here is a number of other true statements that are derived from it. Oh yeah. So so so it goes axiom then theorem then lema then corollary. That’s apparently how it goes. So like you said, axioms are self-evident truths assumed without proof. Theorem is a major proven statement. Lema is a minor proven result used to help prove a larger theorem. A quotequote helping theorem. A corollary is a direct easy consequence of an already proven theorem. The key difference lies in their roles. Axioms are starting points. Theorems are major findings. Lemas are stepping stones. And corollaries are quick follow-ups. I like that. >> Okay. Nice. >> I didn’t I don’t know. >> Click that. That’s useful. >> Interesting. Yeah. >> Okay. We can get back to it. >> Cool. Uh so Chinese remainder theorem. Um we actually might have time to get some exercises. We’re 30 minutes in. >> Um well, we’re 40 minutes in. I guess we started early. Whatever. The Chinese remainder theorem is a fundamental result in number theory that provides an efficient method for solving congruent systems. It allows one to decompose a complex problem with large integers into several simple problems with smaller modules. This this decomposition reduces the required computational complexity. There you go. Especially when working with large numbers and is widely used in areas such as modular arithmetic, cryptography, and algorithmic number theory. So, uh, that’s something that’s I think generally people should look for when solving problems is the ability to decompose that problem into smaller problems that you can then solve like like one at a time. Um, that’s like always the strategy when trying to solve problems that seem really hard is how do I deconstruct this problem into smaller problems, solve those independently, and then recombine them to get to the larger problem. So people will at you for vibe coding things because it’s uh it’s way more code than necessary more often than not. >> Yeah, I guess you’re doing it wrong. >> And it’s it’s not Yeah. I mean you’re you’re just telling the computer, hey, make it make it so >> Yeah. But it’s also like if you can tell the computer >> Yeah. >> to make it so subject to these >> Yeah. Yeah. Of course. Then you get a better hopefully you get a better answer. Yeah. Yeah. Yeah. Yeah. Yeah. other than like hey man you know like instead of saying like make me this thing >> that’s why pre-planning is >> make this thing using react so it doesn’t reinvent react in the process of making >> yeah exactly exactly >> here’s an example uh did it even show them oh did I miss that what happened here um suppose there’s the following system um x congrent to x1 x congrent to x2 mod n2 x congrent to xt mod nt Okay, where uh n sub1 to n subt are pairwise co-primes and x1 to xt are fixed numbers. Okay. Um then this system has a unique solution modulo n equal to the product of n1 to nt. >> Mhm. >> Um in fact we can easily find such a solution. Let n subi equal to n / n i think there’s a way to say that which I forgot previously. Since n1 to nt is our pair wise co-prime we have greatest common carious common denominator of n i and little n i equal to one for each i. So by the extended uclear there exists an ai such that we just did that one. Um thus the solution is given by this linear combination of these factors. So that’s interesting. That then is the decomposition of interesting. This expression provides the unique solution modulo n where n capital n besides using this idea we could write an efficient algorithm to compute x knot iteratively. So like this allows you like to decompose these like given these things are true you can decompose this large problem into a linear combination of smaller problems and then solve each of those ones separately like the A1 capital in some one like this part here is a part of the decomposition >> and so when I say linear combination I mean this part >> yeah just adding the products yeah of each of each step like A1 N1 1 x1 + 8. >> I’m looking at this. So where >> shouldn’t there be a parenthesis around the entirety of this thing before the mod end or is that assumed or applied? >> It’s applied. I think at the very end of the statement when you do mod in it’s just like this whole system mod in >> okay. Okay. So first of all we find n is equal to so we define capital n 5 * 7 * 11 which is equal to 385 and we compute n sub i capital n sub 1 is equal to 7 * 11 n sub 2 is equal to 5 * 11. Okay. And the last one should be five and sub3. Five and seven. So you take the product of the other two for any given n subi. It’s the product of the other two. Right? You see this um I’m reading um reading along behind you. So first of all we find n is equal to 5 * 7 * 11 is equal to 385. So that is your >> capital N >> your a ntxt format I suppose. >> What the do I do? How do I do that? That’s interesting. >> Then we compute n subi and one. So that’s the first term. So seven where did they seven do that? 7 x * 11 7 * 11 n is equal to 5 let’s see so we have that n is equal to n1 n2 nt n1 n2 nt so 7 5 711 n1 one. Why are they pulling from N2 for N1? 7 * 11. >> It’s the product of the other two >> co-prime. >> Oh, I see. I see. I see. So, okay. Okay. Okay. Okay. I see. I see. Okay. Okay. 5 * n2 is 5 * 11 and then n3 is uh 5 * 7. Okay. Okay. Simplify calculations. We give inverse for granted. A1= 3. A2= 6. A3= 6. To simplify the calculations we give inverses for granted. >> I’m just saying like we’re going to give you like just simp. >> Okay. So 366 solution is then given by x sub0 is equal to 3 * the and one. So 77 * uh 1 which is x= yeah x cong >> then the next one 6 * 55 * 2 okay I get it congruent to 1521 congruent to 81 mod 385. How did they get the 81? They just solved it. No. Where’s the 81? >> How did you get to what? The 81. >> Yeah. Where’s that one coming from? >> It’s just like I think it’s just solve >> it. Just solve it down. Okay. Okay. >> Yeah. So, it’s like three here. Let’s just >> So, it’s going to be like 81. But do a 15 21. >> Huh. >> Uh mod 385 should be 81. 15 21 >> mod 385 >> 385 >> That’s probably going to give you 81 as a remainder. >> Oh, nope. I’m I’m I’m not using this calculator correctly. 1521 times maybe times mod. Yeah. Let’s see here. Um pull up my terminal. Nope. Okay. So you can’t write it how it looked. Oh no. 1521 divided by mod 85. >> 1521. >> No >> mod. I think you just got to do 81 mod 3. >> This is three. >> 85. >> Wait, what? >> Remainder. Yeah, we need a remainder. cuz I like it. So I don’t know what’s >> uh 15 21 minus 3 * 385 366. So that’s not right. Oh, you just use triple equals. Okay, let’s get to that one then. Yeah, I’m about to do it. Uh, I’m just going to move on to the not yet. Solve for x. Where are you? Where you where you doing this? >> Uh, wolf from on a on a on a browser. >> Yeah. >> Okay. >> Yeah. >> I’m just writing the expression 1521 is congruent to 81 mod 385 where I’m just leaving 81 as x and saying solve. But that’s not that’s not doing it. So not entirely sure. Yeah, if you do what? What did you get as a result? Because I’m getting 366 because I’m just throwing in the remainder. >> Yeah, this doesn’t make sense. Hold on. We’re doing this wrong. Where is my We just multiplied it all out. Like 3 * 77. Here we go. Let’s do this. 3 * 77. Um, where’d it go? That’s 1 + 55 * 6 * 2 + 6 * 35 * 3 1521. Okay. How is 1521 congruent to 81 mod 35? 385 is the capital N. So we have looking at 1521 congruent to just call it a mod in. It doesn’t look 385. Is there something we’ve learned earlier about this? Have to write down all the definitions for these things in like a cheat sheet to see like >> Yeah. You know. >> Yep. Yep. >> There’s something here we’re missing that we previously learned. It’s like, oh, a is this because of this >> that Yeah. 81 is that because of >> I just threw in a chat GBT because we keep getting 366. Okay. Yeah. I mean even even chat GBT is like this. It’s it’s 366. Hold on. If you try 81 the difference >> to take the whole thing out and then like >> let me take a picture of it and put it in >> I I that’s what that’s exactly what I did. I I took a picture of it. the oh no uh the bottom of it and I’ll put the whole example in this time. I was just like show me how you get 81. It was like it’s 366. Hold on. Show me how you get 81 in this example. >> Did we find a problem? >> Probably not. >> We’re just like I said the notation in this book is a little bit off. >> Yeah. This is why people don’t like math. Yeah, >> let’s just move on. Let’s get to the examples. >> All right, that’s fine. >> All right, Oilers’s theorem. Um, now we are ready to introduce one of the fundamental results in number theory. Okay, now that we’ve built up to this, Oilers’s theorem was discovered by the mathematician Leonard Oiler as a generalization of Format’s last little theorem. Um, why is it so important? Oilers’s theorem is a key result in number theory in cryptographic applications such as RSA encryption and so on. Essentially, it helps in understanding the structure of the multiplicative group of integers modulo n and gives a foundation for other important results in number theory. Besides, it provides the simplification of large exponents in modular arithmetic. The theorem states um a to the f of n is congruent to one mod n for any a that exists within what was that the the congrent set or like It’s it’s a it’s it’s just notation. I don’t know if it’s what the name of that like the >> Yeah, here I can I can I can >> Yeah, it was a it’s a it’s a set of it’s a >> Here I can >> scrolling scrolling >> I’m going to ask GBD for alternative ways of saying that. >> The multiplicative group of integers was the >> ZX subn. >> Yeah. Yeah. Well, multiplicative group of integers. Yeah. 3.36. I see. >> So like I I see in my head I see like the multiplicative group of integers as the basis functions of a given modulus. >> That seems fair. >> That feels like the right thing to me. Right. Given a field over like like when I think of modular arithmetic mod is the field in which you’re operating >> and the basis functions of that field are the is this is this set right of multiplicative integers. Does that make sense? Makes sense in my head. I don’t know if it makes sense to you. >> I get what you’re saying. I just don’t know if that’s how it’s going to be if that’s going to if that’s how it’s going to >> Yeah, I’m very curious to see if right because I’m trying to always I always explain it in terms of linear algebra. Maybe when we get to linear algebra, it’ll it’ll make these connections for us. >> How do I read Also, by the way, Chad GPD said, uh, you don’t get 81 from that computation with modulus 385. It’s a mistake in the example. Here’s the correct reduction step by step. >> So, >> yeah, running in the book. >> I don’t know that it’s I I I I assume >> I’m going to take this problem to uh someone who knows this stuff and see if we’re right. Tell me what Bellage how Bellage interprets their notation because I have a feeling it’s not a it’s not a problem of the math. It’s the way that they intend to convey a thing >> and it’s written wrong. >> Yeah. I’m I’m going to take this to a group of people and get a get an explanation from them. We’ll come back to it next. >> That sounds good. That sounds good. >> Or maybe we can have them on next episode like, “Hey, explain this to us because it’s either wrong or we’re not we’re really not getting it.” It’s like >> Yeah. Yeah. >> All right. Um so lima is suppose a within this set of multiplicative integers denote that um a times it so a is the set of ax parameterized by x within them. Then Z subn equals the A. Oh wow. Element-wise multiplication by A permutes the element. >> So okay. So okay, if you multiply the multiplicative set, it does a permutation on the set. >> It’s still the same set. It’s just permuted. I >> mean that makes sense. >> Why like is it does does does permutation mean something different other than changing it to you? >> It’s more of a rotation. So permutation is more like rotation. >> Okay. >> So it’s the same thing viewed in a different angle, right? >> I see. I see. So when you’re multiplying all these uh what are they? all these subgroups, you’re rotating the the like the numbers within the field. >> Yeah, >> I get I get where you’re going. >> Our statement is equivalent to claiming that the function f goes to a see. Okay. Uh defined as f ofx is equal to a of x mod n is a bjection. To show this, we need to prove the following three statements. correctness is obvious since ax is in a >> are you let me let me just interrupt like for a visual like a mental visual like you’re viewing it like a bunch of clocks getting multiplied by some factor and all the clock hands are rotating or something like that right >> yeah kind of that’s how I’m that’s how I’m kind of intuitively trying to view this >> yeah that’s what I’m I get I get where you’re going >> need to prove that if f ofx of one deal with fx2 then x1 is equal to x2 2 which exists within the set from the function definitions we have ax sub one congrent to a x sub2 mod n the following definition 3.31 you can cancel a modulo n as a is co-prime to n then okay sjectivity I think it’s be subjectivity no subjectivity >> no no this sject sjection is a different one >> we need to prove that every element y within this has at least one pre-image inverse f of y then the set x is defined as a inverse y mod n. This expression is well defined as a is co-prime to n and has an inverse. Therefore f is bjective and thus what we set out to prove in the first place. So we know that this what we just said. How do we proceed? Cool. Um, notice from the set equality follows the equality of the products of all elements. Let’s write down. Oh, I don’t want to say all this. >> Yeah, you’ve been skipping some stuff when you’re reading. >> Yeah, that’s just the way my head works. >> Are people actually just listening to this from word for word? >> I don’t know. So the product from i= 1 to f of n of x subi is congruent to the product of uh a I’ll just read it. The products of a x subi from i= 1 to f of n mod n uh how do you read that arrow? I forget like like implies >> can >> like >> implies okay I was can also be rewritten as >> okay >> so it’s like I don’t know >> it follows that like I don’t know >> okay and it looks like it’s the same first term it’s a it’s a product of x subi from i= 1 to f of n is congruent to uh and there’s like a factor extracted out >> from uh what looks like the second term which is >> yeah so outside of the product. Yeah. So a to the to the f of n. So f of n is an exponent of a times the product of x subi mod n from i = 1 to f of n. Since all x subi are co-prime to n by definition, we can cancel out the product of all x subi from both sides leading to the conclusion of Oilers’s theorem. Example 3.21. Let us consider how Oiler’s theorem works. By computing seemingly scary expression 29 to the^ of 202 mod 13 by means of definition 3.41 we have 21 or sorry 29 to the f of n is congruent to 1 mod 13 uh where f of 13 is equal to 12. Using this let us try to simplify the expression. So 29 to the^ of 202 mod 13 is congruent to and then they have a algebraic simplification here of 29 to the power of and so they’re expanding the exponent 202 into 12 * 16 + 10 mod 13. Then they have uh the first they can they can pull out the term 29 to the 12 * 16 as a term that cancels out. So they’re just left with 29 to the^ of 10 mod 13 and then 29 itself they simplify that to 3 to the 10 mod 13. There’s a lot of >> why does the 29 >> simplifications here? I don’t know how they’re doing that >> cancel out. >> So yeah, I don’t know. That’s probably in the definition above and we just didn’t grasp that. I don’t think that’s something that you can work by hand. You just kind >> There is the one that I’d like to understand the canceling out. >> That’s fair. Um, let’s see. Let’s go back up here. >> I guess it’s like they they only care about the remainder in this, >> right? >> Let me let me >> I need to go up to go back down. So like for instance the out the conclusion that they make after the example they have three mod 13. In other words we significantly reduce the computational complexity by using Oilers’s theorem. Now let us consider one essential coralary of oilers theorem which is used in finite field arithmetic. If p okay corlary 3.43 if p is a prime number and a is not divisible by p then a to the p minus one is congrent to 1 mod p. This result is commonly known as ferment’s little theorem. However, to maintain generality, we state the theorem in a more general form below. Okay? So, like there’s something up here to get that. Let’s go back to your question. 29 to the power of 20 of 12 * 16. There must have been something up here. Maybe it’s this right here. So, um f of 13 is equal to 12. This it’s right here. It’s right here. >> Here. Um so in the in the expression where they had product of primes. >> Yeah. So so in example 3.21 they have a line that says where f of 13 is equal to 12. Now if you go up you go up to the line where it’s the product of uh x subi >> from i= 1 to f of n. It’s like the the the right half of the expression above. >> They they pull out that a to the f of n and that a to the f of n is f of n is 12 there. So that’s how they get 29 to the 12. You can cancel that out. But the to the 16 I guess that one I’m not sure how they got the 16. >> Looks like 12 * 16. >> It might be the same. It might be like it might be um >> the modul right like 202 like 12 * 16 is probably 192 >> because they’re both even. probably it’s >> yeah we’re both on 16 there’s 192 so like >> I think I think that’s what it is >> like factor it like that >> so like if you look at 202 mod 13 like 10 12 well but like think about it this way like like I know it makes sense to you but like for me I could just say 12 29 to the 12 it’s just that times 29 to the 12 16 terms of that and so each of those >> Yeah. So like it’s just it just brings around the clock, right? >> It’s just one. Exactly. Exactly. >> So like who cares? We only care about the remainder in this particular thing. We’re just >> It all simplifies to one. >> Yeah. Yeah. And that’s how they just cancel that out. >> Okay. That makes that that’s intuitively okay to me because you’re just like yeah it’s like like based on all this math we’re able to do this in the exponent and then cancel it all out because like those those are I think >> I’m going to look at there’s a couple videos um from three brand one blue and watch labs on Oilers’s theorem. >> Yeah, that would be that would be good to include in the show. >> Those are usually around like the the main I guess instantiation of this is e to the i pi is equal to minus one. Yeah, I want to I want to see it I want to see that explanation in this >> language. I’ll play around off off camera probably because we’re almost out of time. >> The rest of it is kind of just >> looks like it’s just like factoring down. >> Yeah. Yeah. Everything after the first two lines is just it’s just what we’ve done before. The 29 to 10 mod 13 it’s the same thing. >> Yeah. I imagine I imagine 29. Uh >> so it’s like first reduce the exponent from there reduce the >> well you have to factor it first. So it’s like like you’re taking 2002 which is the exponent and then trying to factor that into uh something that’s an exponent of 12, right? 12 times something. >> Yeah. >> And then from there like the 29 to three I actually don’t know how they got that one. So what would that be? Oh no, it’s just mod 13. So you’re just doing it’s three. It’s 26 and it’s three. Yeah. Okay, that’s fine. It’s >> like there’s there’s like ways in which you can keep reducing things in modular arithmetic like by by only focusing on >> the thing that’s exponentiated or the exponent itself. >> Yeah. >> Right. They’re separable in a way. >> Yeah. Yeah. >> And that’s like the key I think it insight is that these things are separable. So you can work on them independently. >> Yeah. and then recombine them and then solve that problem. >> Yeah. >> Because if you look at what happened in the first couple steps, >> we’re basically ignoring the 29. We’re only dealing with the 202, >> right? >> On 13, >> right? >> Yeah. >> And then get rid of those factors. Gives you a small number. >> You’re just trying to decrease the really big number into a smaller number that you can find other going through are >> Yeah. >> proved methods for how you’re able to do that, >> which is interesting. So you have a theorem that gets proven and then you’re using the theorem to pattern match reduction of the expression from big number to smaller number. >> Yeah. >> Faster. Yeah. >> Cool. Is that a good place to leave off for next time? >> Um no we have just a tiny bit here. Just a tiny bit here. Right. So let’s just run through these coral areas. >> Other words we significantly reduce the computational complexity by using the Oilers theorem. Now let us consider one essentially essential coral area of oilers’s theorem which is used in finite field arithmetic. If p is a prime number and a is not divisible by p then a to the p minus one is congrent to 1 mod p. Seems very similar to like we previously said um on like the the uh fee is of a prime is like one minus the prime. >> Yeah. Yeah. Yeah. >> Multiplicative set kind of. >> Yeah. if it’s prime. This result is commonly known as formats little theorem for ma formats whatever you say it however to maintain generality we state the theorem in a more general form below let p be a prime number for any integer a the following holds a to the p is congrent to a mod p um the proof of form’s little theorem is a direct consequence of oilers’s theorem we can consider oilers theorem as a generalization of formas little theorem Okay. Moreover, this fact allows to find the modular multiplicative inverse of an integer a modulo prime number faster than using the extended uclear algorithm. Um, corlary for any integer a and prime number p, the modular multiplicative inverse a inverse mod p is a p minus 2 mod p. Interesting, man. There’s there’s got to be some really cool visualizations that help give intuition here. I’m going to go on a deep dive of >> Khan Academy has >> brown one. See if I can >> Yeah. Okay. They probably have really nice ones. >> His visualizations are just beyond. >> Yeah. Yeah. Yeah. >> He he has an interesting way of like taking it to a different field, explaining in that field, and then making the connection back. Interesting. >> Um, Welch Labs, I think, does a really good job of this, too. But that’s those are usually one >> Welch Labs. Those are usually in the context of AI and large language models and demp like that type of thing. >> You say Welch Labs. >> Yeah, Welch Labs. >> Okay. >> Um, >> okay. Proof. Notice that um a do a p minus 2 is equal to a p minus one to 1 mod p from our definition 3.41. Note that computing a p minus 2 mod p requires less than two log two of p modular operations using the fast exponentiation algorithm in python implementation using built-in uh p function looks extremely simple. >> It’s pow. >> Pow. >> I always say pow. It’s a power function. Yeah. Power function. So inverse uh so a the inverse of a and p is return. Well okay power a p minus two of p. >> Yeah. Yeah. Yeah. >> And then we’re in exercises. Maybe we just do all the exercises. We like we’ll like figure the stuff out. >> And we’ll just do all the exercises next time and then we’ll actually get into the abstract algebra part. >> That would be actually really good. Yeah. If next next session we try to do all the uh exercises separately and then we come together and run through them on camera. >> Okay. And like explain them to each other. >> Yeah. And then the next the next time we meet the week after we can do the next section. >> Cool. >> All right. Good job. >> Homework. That was fun. I know. >> I enjoy that. industry.