What is a Relation
https://www.youtube.com/watch?v=1v0qH4l9A2c&list=PLg8ZEeSiXsjgoQJzRcq60GjK0UrkMsA3-&index=12
What is an Equivalence Relation
https://www.youtube.com/watch?v=o-PhSZztHC0&list=PLg8ZEeSiXsjgoQJzRcq60GjK0UrkMsA3-&index=13
Modular Arithmetic (a little advanced but its good support until I find something simpler)
https://www.youtube.com/watch?v=d-n92Ml1iu0&list=PLDDGPdw7e6Ag1EIznZ-m-qXu4XX3A0cIz&index=78
Fundamentals
npub12eml5kmtrjmdt0h8shgg32gye5yqsf2jha6a70jrqt82q9d960sspky99g
AverageGary
npub160t5zfxalddaccdc7xx30sentwa5lrr3rq4rtm38x99ynf8t0vwsvzyjc9
In this episode, we delve into the intricate world of cryptography, focusing on the mathematical foundations that underpin modern cryptographic systems. We start by exploring the AES chapter from the "Understanding Cryptography" PDF, discussing the layers beyond the mathematical sections. Our conversation highlights the importance of understanding both the cryptographic implementations and the mathematical relevance behind them, particularly in the context of public and private key cryptography, such as RSA and elliptic curve cryptography.
We emphasize the significance of modular arithmetic, describing it as a fundamental substrate for cryptography. The discussion includes personal anecdotes about internalizing modular arithmetic and the continuous learning journey in understanding its applications. We also touch upon the Euclidean algorithm and its role in finding the greatest common divisor, which is crucial for cryptographic functions.
The episode further explores the concept of cyclic groups and their relevance in cryptography, particularly in how they can reorder elements to enhance security. We discuss the importance of understanding linear combinations and equivalence relationships, which are foundational in mathematical modeling and cryptographic analysis.
We also address some errata from previous episodes, clarifying definitions related to binary operations and cyclic groups. The conversation is enriched with practical examples, such as prime factorization and its role in cryptographic algorithms.
Finally, we express gratitude to our listeners and those who have supported the podcast through boosts, encouraging them to engage with the material at their own pace and to explore additional resources provided in the show notes.
[00:00:00]
Average Gary:
So, yes, I was going through the AES chapter, the understanding cryptography PDF. And it got to the point where it's, like, talking about the different layers and everything like that, but this is beyond, like, the math section.
[00:00:12] Unknown:
Yeah. I don't think that well, from my from my standpoint, I'm like trying to bring I'm I'm on the math side of this. Mhmm. You're so I would ignore almost all of the implementations of current, you know, current crypto systems that don't, you know, I think if you like, I defer that to you. You are the you are the cryptography side, and then you would be asking, you know, what is this, you know, what is the relevance, What's the mathematical relevance behind x y z? And at the moment, I probably have a hard would have a hard time. I don't remember AES. RSA is something that has an obvious,
[00:00:53] Average Gary:
obvious relevance because of modular arithmetic and discrete logarithms are such a Well, that's the public private key cryptography thing. Right? So, like, the AES is a symmetric cipher, and it's also a block slash stream cipher, like, combo thing. But, like, the block and stream cipher piece of that is I don't wanna say irrelevant to the public private key cryptography, but it's it's different considerations. Right? Like, it's good to understand those groups and everything like that and, like, those those basic math things. But when you were looking at, like, elliptic curve cryptography, I think it is distinctly different than, like, a stream cipher.
Right? Like, it they're 2 different things.
[00:01:35] Unknown:
And elliptic curve cryptography helps answer it actually would help answer the question of why the math is important. The implement these implementations are more, I think, to understand the general, just this general idea that you have a party that wants to encode plain text into ciphertext and wants it to be decoded without, you know, without attacks. So, like, I think that is like a very basic level of cryptography and, you know, you have the linear transformations and the affine transformations, like the old Caesar cipher to go through some of that. So from I would say, like, those are kind of interest those are useful in showing why modular arithmetic just matters for at the most basic level. Yeah. I am I am on this I am on this revelation kick, and I just posted it out of the motivate the math Noster account that I cannot understate the importance of modular arithmetic. And when I say the importance of it, like, 2 things. 1, for people like us, it's just it's just over and over again becoming as good with it as we did with multiplication and addition. Mhmm. Internalizing it because there's no it's, a, it's so powerful and it's such a big part of why crypto why the cryptography we use works, but, b, it's it's needed. It's just it's substrate. It's total total substrate for it.
And I have you know, I'm like 2 years into my rabbit hole on this. And, God, I wish I brought my notebook down to show you on screen. Just the mountains and mountains of modular arithmetic I've done just in notebooks where I'll sit somewhere where I'm going to wait for like a couple hours. And remember the exercise I did last week when I was talking about a cyclic group where I was saying, oh, it's 2 you'd start taking the powers. Mhmm. 2 oh, by the way, we do have we I have smaller rata, and this is one of them. But, you know, you take 2 to the first power, 2 to the second power, 2 to the 3rd, and then you keep so, like, I have these notebooks where I I go all the way up the prime numbers up to as far as I can. It's just as far as I can. So I'll have a prime number like 53 and I'm testing every single number to see if it generates like the group 0 through 52. I like Oh, wow.
Like that is Yeah. Yeah. The level at which I that I am trying to internalize this, and I can see it. Every couple of weeks or so, I can just see I'm getting better, faster, more adept. You know, it's like Yeah. You learn it's like learning a lay up and then you learn how to take a little hook shot and you learn how to take a jump shot and eventually, you know, the more you do it the more the better you get at it. Right. And then it because what you know, then I go through then we decide to do this podcast. Right? And as you guys know, I'm not a math PhD. Right? I only just started learning stuff 2 years ago for the most part. Mhmm. And I have this book written by Neil Kablets that is modem that that called it's called a course in number theory and cryptography, and it's a graduate text. But it is the thing I've been going through to see now where, you know, where is math being used in cryptography because this is a math book for cryptography.
And, I have to tell you, like, going through that book now versus going through the understanding cryptography book 2 years ago, it's like a different story. It's like I've leveled up like 50 times. And a lot of it is I can tell you a lot of it is the work I did just sitting down doing arithmetic. And when I say, you know, we say modular arithmetic, it's like, yeah, you take you find an n that you want to have mod and you just play you find you you take any number and try to find the inverse. Right? That's a great exercise right there. So let's say you have mod 11, and you want to take the inverse of the number 2. You want to take And what do you mean by the inverse? What what does that mean? Inverse is, remember, like dividing.
Right? And in abstract algebra, you remember we had the we had those 4 axioms where there existed an identity element, and then there exists an inverse. Yeah. Yeah. It's you to the identity element. Yep. So in multiplication, and a lot of times I'm assuming multiplication without saying it, and that's where I got in a little I think purists purists are going to be angry about how I talked about cyclic groups last week because I just assumed multiplication. But like in multiplication, your identity element is 1. And so you want to say, I have an element that I want to find the inverse of, so I have an element like 2. What what number should I multiply by 2 in model 11, right, that the answer would be 1?
[00:06:38] Average Gary:
Now listen to Hold on. Say that one more time.
[00:06:41] Unknown:
So what number multiplies 2 that gives me an answer of 1 Model 11? There's only 10 possible choices. Right? Is it yeah. Hold on. So yeah. I'll sit with it for literally, sit with it for a second. Start cycling through. I think it's almost I think it's 6. It is 6. That's right. Yeah. Right? So so just for to verbalize it for the transcript, 2 times 6 is 12 which in mod 11 is 1. So that means that 6 is the inverse of 2. Meaning, when when you wanna divide 2 by 6 in the space, like, basically in the finite field mod 11 Yeah. You're actually well, it's not it's actually 2 times 6.
Dividing is Is 1. Yeah. Dividing is multiplication. And it's funny, on on, Rock Paper Bitcoin, which hasn't dropped yet, I had a whole thing about all the new podcasts I was doing. And I was told a story about my grandmother telling me that, love does not divide. It multiplies. And finite fields are like that too. You're actually Okay. So that you're multiplying to divide.
[00:07:54] Average Gary:
Yeah. It's like Columbus going east to go west.
[00:07:58] Unknown:
The inverse is What? Other way around.
[00:08:03] Average Gary:
The element times the element to the power of negative one Well, hold on.
[00:08:09] Unknown:
Equals 1, though. Let's just take our normal arithmetic. Right? If I have one of the inverse of 2 in, like, the real number system, then the answer is 1 half. No. That's for under addition. Sorry. Under addition is negative 2. Under multiplication. Oh, yep. Okay. So under multiplication, it'd be 1 half. Right? Because that's the number I multiply by 2 in the number system I'm in to get 1. But if I'm in the number system, which is basically it's called it's called the quotient group of the integers, model 11, let's just say, which is my now it's which is a set of numbers. Why is it a quotient group? Quotient is the It's it's just the name of it. Well, it it's called the quotient group. And in this case, z divided by 11 z.
[00:08:59] Average Gary:
Right. Yeah. Because quotient is the term for the answer of division. Right?
[00:09:05] Unknown:
That's it is term. Yes. It's term and division. I wouldn't think too hard about it right now. I would focus on the the group we're so the set of numbers we're now in. Right? Mhmm. 0 through 10. Right? And in that set of numbers with those with with the operational multiplication in this, right, in this quote unquote group.
[00:09:29] Average Gary:
Mhmm.
[00:09:32] Unknown:
If I have the number 2 as a member of my group. Right? And the number 1 is a member of my group. But what's the number number 1 is a very special member of my group. It's called the identity element of my group. And so I want another special member. There's another member of my group called the inverse that I know if I multiply by 2, I get the answer of 1. And you just figured out earlier that that number is 6.
[00:09:58] Average Gary:
And the, let me let me try to think of this. The inverse though but this is strictly speaking though for a quotient group, meaning a group based on the operation of multiplication.
[00:10:13] Unknown:
Well, now is that inflate don't I would not inflate the name. If I'm almost sorry I said it. Okay. Oh, it's alright I said the name. For the group that we're in, which is this finite field model, and it's like model 11 Mhmm. Which consists of the elements 0 through 10, not the numbers that integer 0, 1, 2, 3, 4, 5, 3, 10. Right.
[00:10:35] Average Gary:
Right? Now is there any relation between the identity element and this inverse or is it is one always used as the inverse?
[00:10:48] Unknown:
Well, the one the number one is always the identity element if the operation is multiplication.
[00:10:55] Average Gary:
Okay. Yeah.
[00:10:57] Unknown:
Someone's gonna correct me on that one. I'm sure. For that for math, I haven't studied yet. But, like, that's generally what we could say to ourselves.
[00:11:06] Average Gary:
Because one times an element is itself. Yeah. That's right. Right. So
[00:11:13] Unknown:
the inverse is always the number that multiplies an element of the group to get back to 1.
[00:11:21] Average Gary:
Okay.
[00:11:22] Unknown:
And it doesn't always exist. Right? So then you don't have a group. But, like so in other words, for example, you can't divide by, like, you can't divide by 0.
[00:11:35] Average Gary:
Right.
[00:11:36] Unknown:
It doesn't you know, there's not there doesn't always exist an inverse. Then that's the difference between, say, a ring and a field, not that we haven't gotten into that yet. But a field is has is restricted in a lot of different ways. One of which is that an inverse it's called an integral domain and that there always is a number. There's always there always exists an inverse. I I think I could be screwing this up. But I'm pretty sure that's the case. And and that's the case in in what context, though? Right?
[00:12:08] Average Gary:
So there is what do you mean? Like, is that the case in certain
[00:12:17] Unknown:
groups or certain fields? Definitely certain groups but of I believe all anything called a field, there are certainly at least a finite field. Mhmm. So and this is some any at least a finite field is always going to have, I believe it's always gonna have an inverse element.
[00:12:37] Average Gary:
Well, because a finite field is defined by modular arithmetic.
[00:12:41] Unknown:
Well, yes. But really it's see this I started talking about this last week. There's this there's this chain. Okay? It starts with starts with defining a ring, which is a variant it's like a variant idea of a group where that there's 2 operations instead of 1. They're both defined. 1 is definitely addition and the other is definitely multiplication. Right? And in the most general version of what you call a ring, the group axioms are true for addition but not multiplication. Okay? So you have like you have all 4 group axioms for addition, but for multiplication you only have closure and associativity.
You certainly don't have necessarily unity or what's called like the number one doesn't necessarily exist. So there's a ring called the ring with unity where it does exist. And then there's something called the commutative ring where, A times B equals B times A. That property exists. But that's not necessarily it's kind of like remember when we said groups don't have to be abelian? Groups don't have to we define an abelian group that's commutative on the operation, meaning from a left rightness perspective, A operates on B is the same as B operating on A. So basic groups are not necessarily commutated, but they can be.
Rings are always commutated for the addition operation, but not necessarily multiplication. You have to specify that that's the type of ring you're working with. And how is that specified then? You call it a ring with, a commutative ring. Right. So you say now I'm specifying that I have a commutative ring because the most general version of a ring is not necessarily
[00:14:33] Average Gary:
community. Okay. Alright. And you're just saying the when you specify that, you're just meaning that this ring has this additional property. Yes. And then there's a chain
[00:14:44] Unknown:
of properties that if they're all met, you actually you have a field. Mhmm. So you have a very specific version of a ring. It's kind of like you have you ask everyone in a room, say You're all rings, and everybody raise your hand. And then you say, how many of you are commutator? And then a bunch of hands go down. And then you say, how many of you have the unity element? And a bunch of hands go down. Then you say, how many of you where, if I have 2 numbers multiplying equal to 0, one of them has to be 0. Right? A bunch of hands go down, and then you continue this process. And at the end of the line, you get you say, you sir are a field.
Everyone else is still is a ring. Everyone in the room's a ring, but you sir, who meets all of these, there's probably in the book that I sent you the picture of, there were 6 different, variations of what a ring is or restrictions.
[00:15:45] Average Gary:
Now are these rings used for different purposes? And I'm assuming that well, let me not say. I'm assuming are are there different purposes for these rings, but then do we only care about the rings that are fields for cryptography?
[00:16:00] Unknown:
Yeah. I think what we care that they're rings so that the that the like, I had this cop out statement yesterday. We could do, like, magical math if we know something's a group. And if we know something's a ring, we can really work with it in a powerful way. Mhmm. We own so we work with fields. Okay? But they the fact that certain things are rings is important. And I don't wanna get pedantic about it. But, like, here here's an example. Okay. So a lot of times with rings, you look at polynomials. Should I not take advantage should I not assume we know what a polynomial No. Let's not assume what a polynomial is. So a polynomial is something, you know, we learned about in, probably middle school that is like, ax squared plus bx plus c is an example of a polynomial.
It's an order of 2 polynomial. Right. The polynomials of the form some, a k a sub k times x to the k plus, so in other words, some some some actual number times x to some power. Right. Right? Plus another number times x to one lower power, dot dot dot down the line,
[00:17:30] Average Gary:
some factor some number times x plus some other number. So in other words I think the most like the This is hard to explain. This is easier to If we put it in a bitcoin let's put it in a bitcoin context. Right? There's this the the equation, the polynomial equation that describes the secp256k1 curve that is used in bitcoin is y squared equals x cubed plus 7.
[00:17:54] Unknown:
Yep. So that is an example of That's a polynomial. Yes. But the most beautiful example of a polynomial actually is an act is a digit itself. So like in base in the base ten number system, you know, any every number is actually a polynomial because, so like for example, the number 256 is 2 times 10 squared plus 5 times 10 plus 6. So, like, the numbers themselves and that's why when I say it matters that we know they're rings because the numbers that are actually going into this thing are polynomials and we know polynomials are can be rings.
And it actually is why we can do all this. It's one of the reasons. It's pretty fucking cool when you when it unpacks. But a number itself is a base base something polynomial. Right? Right. A binary number, right, is a is so the coefficients right? So you have so in a polynomial of coefficients, which is like the did the digits were 2, 5, and 6. Those were the coefficients. 2, 5, and 6 were the coefficients, and the x's were the base, 10 squared plus 10. Yeah. And so you see this in base 2 the same way. Right? The number 111 is, you know, 2 squared plus 2 plus 1 which is 7. Right? Number 111 in base 2. If you I took f f in x. Right? Yep. That's 250 that's 16.
That that, you know, right? That's, 16 times 16 plus 16. Plus 15. I'm sorry. Plus 15. So it's 15 times 16 plus 50. So all of the numbers are polynomials. Right?
[00:19:47] Average Gary:
Yeah. It just depends on what base you have. In a certain base. Right? This makes sense again in the AES section of the of the understanding cryptography book. It goes into saying, it was trying to represent I can't remember the exact terminology. It was trying to represent this numerical value, but it wanted to use modular arithmetic. But the problem was it what did not have a prime for the mod number. Right. And so, what they did was they used the the Galloi or the Galois field of base 2 and they converted the numbers to a Galois field of base 2 representing a polynomial.
It was more of it used 8 bits so eight sets of, ones and zeros, which had some implication on, like, the hardware and software side. But then the different aspects of the polynomials, you would the coefficients were the ones or the zeros. So in the example that you just said where it's like 111 is actually 7 the 111 representation of this group that was being represented was actually X squared x plus x plus 1. Yeah. And if you did 10011001 so just put a one at the front and the end of the 8 bits and then 2 ones in the center That turns into x to the 7th. Yeah.
And then You're dropping my memory now. It was It would be x to the 6th, but that's time 0. So you just nullify it, drop it. It would be x to the 5th, but you nullify drop it because it's multiplying by 0. So x to the 7th plus x to the 4th plus x to the 3rd. Right? So you have that first one, which is x to the 7th, and then the x to the 4th or the 3rd. You drop the next 2 plus 1, and so the final result of whatever that number is. And it it was just a way, I think, of, like, taking a group without, like, a prime modulus and applying something over it that does because 2 is a prime number.
That's right. You you're able to have these properties of a a Galois field.
[00:22:10] Unknown:
Yeah. And 2 is prime to every odd number. Right? So that's the other that's the other one. We haven't gotten to this yet because I haven't gotten in any numbers. Yeah. But, like, the idea of a number being prime to another number has to do with this concept called greatest common divisor. It's really important and it's this goes have you you've ever, you know, you hear me all the time, Gary, when I'm talking to you and texting you, going through saying these words, division algorithm, Euclidean algorithm Yep. Greatest common divisor, congruence, modular arithmetic. This package of things is, really where the sauce is at.
And And the Euclidean algorithm was what I reviewed last night. Right. And so the Euclidean algorithm is the way to find the greatest common divisor, not to get too not to get too cute right now, but I only recently discovered from this Caballus book that it's how you also get the inverse element of like when you can't just multiply 2 and 6 in your head and know that that's 1 more than 11. When you say you can't because you're dealing with large prime numbers. Yeah. I'm telling you what find find the inverse of, you know, 722 mod, you know, some prime number that's 5 digits long.
It's like you're not gonna do it without there's just no way. You can't even sit with a calculator long enough to test all those numbers out. Right? And the Euclidean the Euclidean algorithm, we will we will spend time on this. I promise.
[00:23:42] Average Gary:
Mhmm.
[00:23:44] Unknown:
It's so powerful because you can a, find the greatest common what it does is find the greatest common divisor between two numbers. Mhmm. But, it leverages something called Bayesout's identity where now you have you also it means that the greatest common divisor is also a linear combination of the two numbers, which meaning like if I have two numbers, any two numbers, then we'll we'll use small ones like 57. Right? We know the greatest common divisor of 57 is 1, which actually means that they're prime to each other, meaning they have no common factors. K? Right. I can also say that 1 equals a linear combination of 57, meaning I can take any two numbers x and y and multiply 7 x plus 5 plus 5 y. I can always find a combination that equals 1.
[00:24:40] Average Gary:
Alright. Hold on. Let's unpack that. The you said it's a linear combination. Yes. Which is The linear combination means and is it linear because you're taking an x and a y and that that implies a point on a plane? Yeah.
[00:24:56] Unknown:
And it's also one dimension because you're just multiplying by 1 like, pow to the power of 1 variables. Right. Right. Right. So it's just that's that's what linear means. Linear means you're multiplying by an x to the one power. Whereas, if you're multiplying by some if you have a a polynomial that goes up to x squared, that's considered quadratic. X cubed is considered cubic. So back to the greatest common divisor being 1, say of 7 and 5, and I can always make a combination 7x+5y equals 1. And in my head, I can tell you if y is 3 and x is negative 2, that that does it.
But Yeah. Right? So if we just slow down at negative 14 plus 15 is 1. But I know because of Bezout's identity and the Euclidean algorithm, I know I can find the linear combination. I'm gonna do, like, a lot of problems. I'm working on getting set up to do this. It's really powerful. And the fact is, it's what's important to know is that you can do that even when the numbers are just so big beyond your reach. And that's why that's why, like, these little ingredients matter. Is so that you have absolute confidence that you're doing the right thing, even though there's no way you can confirm in your head that you're doing the right thing. Like when you when you're taking 3 digit numbers to the power of another 3 digit number and you're you're actually doing it.
You you don't even have a calculator that you or Excel. There's nothing. There's literally nothing where you can visually verify you're doing the right thing. You you must be able to rely on the math. You must know. The properties of the underlying math. You must. Yes. And because it's the only way. Right? You're it's like you learn how things work on earth and you go into outer space and you go do it and you without without the benefit of gravity and you have to know you're doing the right thing.
[00:27:03] Average Gary:
Yeah. I mean, I I think that like that in and of itself right there is like the reason to motivate the math. Right? It's because if you cannot understand these properties, if you don't if you've not built the context around this to understand what, what do you say, linear combination
[00:27:18] Unknown:
Yeah. And I'm sorry sometimes with the with the with the terminology. In my brain, it thinks it's helpful to say these things, but No. No. It is it is because it's It's confusing, but, like, these are linear combination is something I would just say people should know what it is. It's something it's a term people throw around very, very loosely.
[00:27:36] Average Gary:
Remind me though why in in what context is the linear combination
[00:27:41] Unknown:
applicable and relevant though. Right? Yeah. Okay. So, I mean, any kind of mathematical model. So, y equals mx plus b is a linear was a linear combination. Right? Okay. Yeah. It's a very simple one. But, like, when you try to, you wanna be a chart boy and you wanna say, oh, you know, this is a this is, that something has a mathematical relationship. Like, for example, you wanna model the price of a home, and you've got, you've got a few variables of data. Right? And you wanna decide which ones matter. So what you have is price of similar homes in the area. You have maybe interest rates and you have, give the price of Bitcoin.
You have many things. And then what you'll do is you'll create a linear combination of those things so that you can make your model to predict, like, say, to predict the price of a home. Right? Mhmm. It's gonna be some number times prevailing rate, some number times the price of Bitcoin, some number times the price of gold. Some number times the average median price in the area. And then you would have these statistical things that tell you whether or not those variables actually do matter. Is it because you sort of need, like, a basis
[00:29:01] Average Gary:
starting point for your chart or whatever because that one value is now where you can, like, start from.
[00:29:08] Unknown:
Well, yeah. It's it's bay it's like if you wanna say you wanna determine the value of something Mhmm. And say it's a it's based on the value of other things.
[00:29:18] Average Gary:
Yeah. Yeah. Yeah.
[00:29:19] Unknown:
I'm all I'm saying is a simp the simplest way to do that is what's called the linear combination of those things where you just you don't do anything to those numbers. You don't say, oh, I have to square the price of Bitcoin. Right. I'm just gonna multiply it by these things, x y z. And that's a linear combination. Okay. It's a linear combination. Exactly. And, you know, it's it's a very basic concept. It's probably worth Googling. And, you know, that it that's, it's very that's another one that's like congruence. Like, it's you just wanna know what it means. You know, I talked about I I talked about on Rock Paper Bitcoin. I think it's the one that you called me after to start this podcast when I talked about this term, morphogenal divergence.
Yep. Okay. So what that was all about was that, knowing whether it's like you have one you got one system that's like a linear combination. And let's just say, you know, in a system, you have a set of information that's absolutely a function of the other information that's in the space. Like, it adds no new information.
[00:30:38] Average Gary:
Right?
[00:30:39] Unknown:
So even though that linear it's like a it's a different it's kind of like, you know, you have these chart boys that add no value because their actual their models are are essentially giving no additional information to It's all deriving from the same context. What's already out there. Yeah. And so linear algebra, the field, right, is very much the you know, it's a way to look at essentially the value of new information coming from a from linear combinations in systems. And this is really like, I'm really feeling uncomfortable with this these explanations. We're good. We're good. Yeah. I don't think they're very good, but We can go back to cryptography.
[00:31:23] Average Gary:
We've said, Chart Boy wait one too many times.
[00:31:27] Unknown:
Yeah. When I say Chart Boy, you're you that should be a signal that I'm about to shit on the math there. Right? Okay. And the significance. But, like, well so crypto so here's the other thing, though, that's related that's here's where it's relevant to cryptography or cryptol I should say cryptology. Right? And there's a is there a difference between cryptology
[00:31:51] Average Gary:
and cryptography? I remember it being broken down because there's cryptanalysis and some other things, and I can't recall the the delineation or the demarcations.
[00:32:00] Unknown:
Maybe we don't care what the definitions are, but the idea the fur like, when you like in this Cobblets book, first page of the book, it talks about, okay. So there's a shift, like a shift cipher where Right. I pick a number between 0 26 and I'm gonna use my I'm gonna code it mod 20 I'm gonna code my my, my crypto tech my ciphertext is gonna be just mod a modded version, a shifted version of my plain text. Right? And so what, you know, what's immediately so after you realize how kind of cool that is, right, they immediately tell you, oh, by the way, anyone can see the most popular letter in the English language, e. So they can use, you know, they can use that to figure out what your most frequent letter is. Right. And then easily back into the, and if they can't figure it out from the letter e, they can add a second letter t.
Right? Every So so forth. And the the but these are these actually are linear these are linear, did I call them linear combinations. Right? Yeah. Yeah. So and they're linear they're they're congruences. In other words, the difference between a congruence and an equality is you might say a x plus b y equals c, but you can say a x plus b y is congruent to c mod 11. See, in the mod in the mod space, it's called congruent because there is not a unique answer. They're trying to they're just trying to say, well, you know, in mod 11, 0, 11, 22, 33, 44 are all the same number.
So that we talk the the terminology is congruent. So when I talk right? I talk about congruence as like the most important thing in module. Modular arithmetic and congruence are like addition, subtraction, and equations. Congruence is a type of equation where we're talking where we're dealing with remainders, right, in mod space.
[00:34:09] Average Gary:
Okay. Because because it okay. I'm sorry if that wasn't clear. No. That's good. And that's a triple line. Right? Yes. That's what that's like 3 lines instead of 2. Ah, okay. Alright. That makes a lot more sense because I've seen that in the text. And now I can put a word to what that means. Because in my mind, I'm like triple equals and that's incorrect, though. That's incorrect. Heck is this triple equal? It's because the idea of equality doesn't necessarily apply to these modular arithmetic
[00:34:38] Unknown:
fields or groups. Right? That's right. Because equality means there's a unique answer. You know? I'm sure I'll get corrected on that. Okay. Equality usually means there's a unique answer. Congruence is just means that they're you're right. It's like you can see there's other areas there's other examples of congruence in mathematics. Right? Like congruent triangles, they don't have the same sides, but they have the same angles.
[00:35:05] Average Gary:
Right? Okay. Yeah. Yeah. Yeah.
[00:35:07] Unknown:
So we missed yeah.
[00:35:09] Average Gary:
What and I was thinking about our example of mod 11 and how we were talking about that. We did, like, the, what was the inverse of 2, which was which was, 6. Yeah. Right? And I was thinking about, like, if you're if you're if you're working within a group, like of addition mod of, an addition group of mod 11 and 2+ 14. Right? In regular base 10, regular arithmetic equals 16. But in this mod Mhmm. It's a different answer and the the outcome is not like, there's no equality in what those outcomes are, but there's congruence when you're modding. Yeah. Because the numerical representation let me what so let's see. What 2 +14, so 16 mod 11 is 5. Right?
So, like, 2 is not equal to 5. Like, that that is not equal, but it 2 is congruent to 5 when used within this modulo
[00:36:13] Unknown:
11 context or group. Yeah. I think a great way to go, you just jogged a memory of is to go back to clock math. Right? Yeah. 3 o'clock is congruent to 3 o'clock, but doesn't mean it's equal because it could be on a different day.
[00:36:27] Average Gary:
Right? Yeah. Yep. That's very true. Or it could be 3 AM versus 3 PM sort of thing.
[00:36:33] Unknown:
But you you you see the point is that there's not equal is very restrictive. Yeah. So and again, I'm gonna motivate here and I'm gonna regret introducing another confusing term. But there is and there is something called an equivalence relationship that congruence satisfies. Relationship is something that has 3 properties that you will all understand. 1 is it's called reflexive meaning like a equals a. Okay. Shout out Ayn Rand, you know? So like if your thing equals your thing, right, if if that, you know, it's that's kind of a trivial example but it's not always the case. So that's the first like that's the first quality.
The second is it has to be symmetric meaning like a equals b means that b equals a and vice versa. So if a equals b means b equals a, then you have equivalent. It's another property of equivalence. And the last property is called the transitor property, Meaning if a equals b and b equals c, then a equals c.
[00:37:42] Average Gary:
Yep. You lost me.
[00:37:44] Unknown:
So oh, well, okay. If I have, the trans that's what the transitor property means. So if I have two numbers, a, b, and c three numbers, a, b, and c. Okay. Yeah. Yeah. Yeah. Right. It's so in other words, if the equality extends, if the equivalence extends, it's what then you have what's called an equivalence relationship if those three properties are satisfied. In other words, have you ever asked the question what does equal even fucking mean?
[00:38:10] Average Gary:
I mean, I have lately when I when I saw the congruence symbol.
[00:38:16] Unknown:
Yeah. So, I mean, there is a notion of equal. It probably in, like, God's world. See, there's probably this notion of, like, well, when a cell divides, it makes a copy. Maybe it's an exact copy. That's a I'm sure there's like, there are things in nature that are equal. Right? Even though we're told there's no such thing. Right?
[00:38:40] Average Gary:
The the there's like a there's a, what is it? Like, Newton's law of, like, every force has an equal and opposite force or reaction. Every action has an equal and opposite reaction sort of thing. Like, there's some sort of equality in that. I mean, like my skeletal structure is in I wouldn't even say is equal, but, like, my body composition is equal to the gravitational force on this planet. Maybe. See, and that's yeah. That's not even that's not even, like, an exact
[00:39:20] Unknown:
thing. Very challenging. It's very challenging to sit here and define equal. Right. So this is my little pet answer to people when they ask things like was math discovered or invented? Because I think that like there are certain concepts God gave us and like the fact that two things could be the same is a concept, but we have no formal way of knowing. So when we define this formal structure to say if 2 things are, we don't even say equal because that's like too, presumptive, but we would call it an equivalence relationship. Mhmm. Right?
That something satisfies an equivalence relationship if reflexiveness, symmetry, and transitivity are basically present. Then you have an you can have an equivalent relationship. So, for example, the the greater than is not an equivalence relationship because it doesn't satisfy all 3 of them. K. Right? Like, it's certainly like if The reflective the reflects the reflective one is not satisfied there. And a greater than b is not that's right. But if a greater than or equal to b, it does.
[00:40:35] Average Gary:
Okay. Yeah.
[00:40:37] Unknown:
But that's because now you have you have you have equality in there. But yeah. So it's a good like, it's a good non example is a greater than b is not reflexive. Right? Mhmm. So therefore, non equivalent relationship. Now mod congruence modulo n is a congruent is a is an equivalence relationship and it's the abstract algebra route enables you to prove these things.
[00:41:07] Average Gary:
And it's an equivalence rate relationship because it has the reflexive and the transitive
[00:41:15] Unknown:
and a mod n equals a mod n. Yeah. Right? If a mod n equals b mod n which could be like 11 mod 11, 12, 22 mod 11, then 22 mod 11 equals 11 mod 11. Right? So it has that symmetry and then it has transitivity clearly. Well, if I have 11, 22, and 33, and 11 equals 22, 22 equals 33, sorry, congruent, then 11 is congruent to 33. That's true. Model well, model 11. Right? They're all equal to 0.
[00:41:48] Average Gary:
Okay. Okay.
[00:41:49] Unknown:
So you have what's called an equivalence relationship. And, so what I was saying before was, yeah, I actually think we like, I think God gave us some notion of, like, that 2 things are the same, but we had to like, that we had to invent. Like, man had to just invent the rules. Somebody I don't know who I don't know who did this. Mhmm. It's pretty it's quite an achievement in the human race, whoever formalized what an equivalence relationship is.
[00:42:22] Average Gary:
Well, because you're yeah. You're you're almost, and this is something I've had for a long time. A belief I've had for a long time is, like, the mathematics is the closest we've come to explaining, like, how our world works. It's the closest we come to the language of God because it's it's our best attempt at explaining what exists in this world and then the relationship between all of the properties of it. Right?
[00:42:51] Unknown:
Yeah. Yeah. And then and then so these acts these these, like, definitions, these axioms and being able to call something a group, a lot of it is really just so that you don't have to,
[00:43:03] Average Gary:
it's kind of being able to save your game. You know? It's like it's it's it's signal over noise. Like, you can focus on like, not not saying that everything else is noise, but, like, without having a lens to look through, without having a filter.
[00:43:19] Unknown:
You would have to prove these things over and over and over again every time you wanted to verify something. And so what these theorems and these proofs enable you to do is, like, it's kinda like save your game. Like, you know, you don't have to redo the whole level every single time Right. To do the thing you're trying to do. Right. Yeah. So you get to sit on the shoulders of what you verified in the past. And that's why that is why when I I that's why I say so completely division algorithm, Euclidean algorithm, Bayes' out to unity Yeah. Yeah.
[00:43:55] Average Gary:
Modular arithmetic and groups. When I see the the the Euclidean algorithm too, I I see that because it it is a pattern of reducing the steps to take to get the greatest common divisor Yeah. No matter how big your number is that you're starting or how big your two numbers are that you're starting with to find the greatest common divisor. But there But it's a division is a linear combination. That's that's the first thing. Right?
[00:44:20] Unknown:
Is that my my number So I have two numbers. Right? It, 57. Right? I say 7 equals 1 times 5 plus 2. That's a linear combination. Right? Of 5 and 2. 1 times 5 plus 1 times 2. Yeah. And then the Euclidean algorithm then takes the 5 and the 2 and does the same thing. Right? It says 5 equals 1 time 2 times 2 plus 1. Yeah. And then that's how you know, so this was this is, it's such a fine thought here. Right? Because we're we're covering we're on like a I feel like we're really surfing the wave and just it's the the line between wiping out and continuing in this conversation is very thin. You know? We're getting yeah. We're getting to that point.
[00:45:14] Average Gary:
But it's good. Like, I feel like we're, you know, I feel like we're actually saying something that matters. When I think anybody any like, my recommendation to try to, like, take it back to to where I was trying to grok this last night, and I think I even messaged you about it. It's like, I I think I even posted on Nasr or something about it. I was like, I needed to go back and learn what factoring was. Right? Like, what is what is prime factoring? Right? And it's this methodology. Like, that is the that is the thing that is the computation that you are making that you're simplifying using the Euclidean algorithm is this prime factorization. And all the prime factorization is is you start with the smallest prime number, which is 2 or or 1. Right? And if 1 is is the only one, and you divide the number that you're factoring by 2.
And then you take that, and if there's no, oh, shoot. What is it? If there is if there's no remainder, then you go to the next prime number. If there is a remainder, you continue
[00:46:16] Unknown:
to divide by 2. Yeah. And so this is again, this is why really the first topic to start with is prime numbers. Yeah. Because that is the atom. Right? Like, that's the atom. That's the smallest unit of of all of this. Right? Everything is is And, you know, every number is some product of primes. Right? And then every number is a unique product, just like every number is a linear combination of its base. Right? Every number is also a product of primes. Right. Right? And that, you can you can and it's unique. Like, it's a unique product of primes that all you can do is change the order, but you can't change the primes.
[00:47:08] Average Gary:
Yeah. Right?
[00:47:09] Unknown:
And that becomes really that becomes really important. It's so incredible what you end up, it's just so incredible what you end up getting. I haven't by the way, I haven't done my Roddy
[00:47:24] Average Gary:
yet. I I I Well, let me let me take the let me take the audience briefly through factoring the number 84 Cool. Because I because I did that. And, and the prime factorization of 84, you get to 2 times 3 times 2 times 2 times 3 times 7. And, the way you get there is you start with the smallest prime, which is 2. You do 84 divided by 2, which is 42. Right? So okay. So there's no remainder. So we continue with 2 being the divisor. So we take 42 divided by 2, which is 21. So then the 2 times 2, and now you got 21 left. Yep. And but now we can't divide 21 by 2 without having a remainder. Mhmm. Right? So now because there's a remainder, we we switch it up, and we we go to the next prime number, which is 3 or the next highest prime number, which is 3. So and then 21 divided by 3 is 7.
You try to do 7 divided by 3, you end with the remainder. So you can't do that. And it just leads you from 3 to 5. You can't again. No. There's a remainder there. It doesn't work. You go back up to 7. We're right back at where we're at, 7 and 7. So it becomes 2 times 2 times 3 times 7. Yep. And that's the prime factor prime factorization of the number 84 using base 10.
[00:48:55] Unknown:
Yeah. So, you know, we'll get to discrete logarithms,
[00:49:00] Average Gary:
which are No. No. No. No. No. Don't. Don't. We're gonna crash on the wave if you just don't even go there. The the reason I wanted to go through this exercise because the prime factorization so we just prime factored 84. Right? 2,237.
[00:49:13] Unknown:
The budget is not supposed to be able to do it by hand so easy. That's the key. That that's Well,
[00:49:18] Average Gary:
with smaller numbers, you can. Right? But I guess what I would point out is 84 is always
[00:49:23] Unknown:
the product of those 3. Really, I'd say those three numbers. 2 squared, so 2 squared, 3 to the 1, 7 to the 1. So it's always a right? It's always a it's always a multiplication of some prime to a power. Mhmm. And it's so for 84, it's always those those three numbers to those three powers. 2 squared, 3 to the 1, 7 to the 1. And no matter what no matter what universe you end up in, it's always going to be those 3. It could now that you could do it in different orders.
[00:49:58] Average Gary:
Right? Right. But to tee up, I guess, maybe the Euclidean algorithm, like, how do you get that? So so we have 84. We figured we private factored that. Finding the greatest common divisor greatest common divisor of 84 and another number, you have to factor that other number. Like 35 for example. Well, in my notes here, it's 30. So Okay. We can go off of that so I can read it. Okay. That works. 30 works. Right. But it's it's so so we've already done the the 80. 84. So now we do 30. So 30 divided by 2 gives us 15. Right? So 2 is the first factor prime factor there.
When we do 15 divided by 2, it doesn't work because we have a remainder. So we have to go to 3. 15 divided by 3 gives us 5. We're at a relatively small prime. So we could do 5 divided by 3, but there's a remainder, so that doesn't work. And we end up just back at 5 and 5, and so it becomes 2 to 2 to the first power times 3 to the first power times 5 to the first power. Mhmm. And so when you compare those numb you when you compare those prime factors, the greatest common divisitor ends up being the product of all the common prime factors.
[00:51:21] Unknown:
Mhmm. So 75 get excluded because Very much benefits visually, but, yeah, keep keep keep keep keep keep keep going. Well well, 5 is excluded because 84
[00:51:30] Average Gary:
does not have that as a prime factor. Right. 7 is excluded because 30 does not have 7 as a prime factor. See it. And so all you're left with is 23.
[00:51:40] Unknown:
Right. So the way again, state it again. On the left side, you have 2 squared times 3 times 7 and on the right side you have 2 to the 1 times 3 to the 1 times 5. So you have 2 to the 1 times 3 to the 1 is in common on both sides. Right. Right? Yep. So 6, that makes 6 your common divisor. And what were your two numbers again? 30 84. 84 and 30. Right. 30. And 6 clearly divides those and it clearly does divide those. And, you know, I would challenge the audience member to see if there's a bigger number that divides both of those. Yeah.
Alright. Now the other cool thing, just to call back, is that 6 is gonna be a linear you can all you can make 6 a linear combination of those two numbers, 30 84. Not gonna do it right now. Oh, yeah. I I am gonna do it right now. 30 times 3. Go ahead. 30 times 3 plus 84 times negative 1. That's 90 minus 84 is 6. Yeah. So Beysaut's identity always works and, it's killer. And it's even it's really powerful when the greatest common divisor is 1. So I'll just leave that. I'll leave it at that. That's a little nugget for next time. Yeah.
Can I hit 2 so can I hit, this these errata are actually relevant? They're not Yeah. Yeah. Yeah. Let's hit the errata.
[00:53:13] Average Gary:
Hit the errata Okay. And then we can wrap it. I want I wanted to cover
[00:53:18] Unknown:
I I immediately posted this to Nasser when I we stopped we stopped rolling last episode because I knew it was an issue. Binary we I talked about a binary operation in a group. Right? Mhmm. Let me I'll just tell you what the binary what it what it actually means. What binary operation means that I can take two numbers, perform an operation on them, and get one number. Again, this sounds so obvious but, like, addition satisfies a binary operation because I could take two numbers, 3+2, and get one number 5. Mhmm. I can do that with multiplication.
I can do that with, there are many operations I can do that with. So, again, that's just technically, that's the definition. I said something different. Okay. Okay. And the but and this is it's why it's binary. It takes 2 inputs. Mhmm. It returns 1. Computer science people probably can see why that matters. Right? Then the other one was we talked about a cyclic group. Mhmm. And I just talked about taking powers because, again, I assume the I assume the operation was multiplication when I said that. But in the operation of addition, you could add numbers and try to get a cyclic group. So in other words, one would generate a cyclic group the cyclic group of integers under addition because you actually, no. It's not true. You'd only it would one would give you the positive integers, basically, because you you continue to add by 1.
I used multiple. I used powers. Okay. There's something I can't I think is really cool about it though and I gave that example mod 5 and we we took 2 to all these powers and kept getting 1, 4, 3, 2, 1, 2, 3, 4, 3, 4. We kept getting 1, 2, 3, and 4 in different orders. Mhmm. And so something that gets done in cryptography is you take one of the generators and you multiply it by all the numbers in the group and what it does is it just changes the order of all the numbers in the group. It keeps all the numbers the same which changes the order. I just want to point that out. It's something that's really cool and it's something that actually gets it's something that makes certain cryptographic, systems work.
Hey. Because the plain text may be like crackable, maybe it's ordered in a certain way. Right? So like for example, this is why I asked you earlier if you knew what the knapsack problem was. I just learned about this today. Mhmm. But if you order everything in a certain way, the knapsack problem relies on a very specific structure where, each it's a sequence that always increases and every element is bigger than the sum of all the prior elements.
[00:56:24] Average Gary:
Mhmm. And
[00:56:26] Unknown:
you can crack that one very easy, but if you change the order around, it's no longer It's problematic. In absolute no no effing way. Okay. Right? And so when you have a group, then you can just multiply all the numbers by by the generator to flip you. And then you have a completely different order. You have a different order. You have all the same numbers, a different order. Right. And you can this is you'll see this with not with, number you know, you do this to numbers, which are products of primes. It's your power where you just change you know, again, the order the order can change around, but you still have the same product.
It's so this notion of a cyclic group and the generator is really important because it's something that actually gets done to flip the order around of the elements of a group to make it harder to crack. I believe you. So, like, the the the way it's ordered yeah. So maybe there's a version of it that's ordered in such a nice way that it's actually really easy
[00:57:33] Average Gary:
to To crack it. To encrypt.
[00:57:36] Unknown:
Right? But the the one that you're decrypting is ordered differently.
[00:57:40] Average Gary:
And it's, like, impossible without secret. Is that the asymmetry piece of it? Yeah. Oh, okay. Right? And so this was, what I'm referring to today was Ah, okay. So if you're using a public key to rearrange the ordering, you need the private key to put it back in the right order. That's right.
[00:58:02] Unknown:
So and and so this was, Diffie and Merkle, and I should tell you in the book, this system was cracked by Shamir whose name comes up a lot. He must be important. But
[00:58:14] Average Gary:
Yeah. I've heard of Shamir. He has a sharding thing for keys.
[00:58:19] Unknown:
I assume that's with a d. Right?
[00:58:22] Average Gary:
What? Sharding? Sharding. Oh, yeah. Not shart yes. With the d. Yeah. Shamir Shards. Secret Shares. For Shares?
[00:58:34] Unknown:
Yeah. Right. Well, so anyway, it was crack, but it's it was like, it really illuminated for me again how cyclic group with a generator can actually be used to take something that otherwise is orderly and very manageable and you wanna make it unmanageable by and just by flipping the order around.
[00:58:52] Average Gary:
Right. It's beaut and so you're saying having a way to reorder it. Yes.
[00:58:57] Unknown:
Yeah. I thought that was, like, a super beautiful thing. So, anyway, that's that's part of my errata. The binary operation is a cyclic group. Cyclic group could be any op it could be any operation. Okay. We usually will always talk about powers and multiplication just in general. That's, like, almost always how we use it.
[00:59:15] Average Gary:
And when you say
[00:59:17] Unknown:
use it, you mean in the application of The generator. Yeah. Generator all and, you know, because in the first of all, we're dealing in a a ring. Yeah. A field which is also a ring that is either addition or multiplication, and we'll usually be dealing with the multiplication.
[00:59:30] Average Gary:
Does this that that does that so that means picking your generator is important then?
[00:59:38] Unknown:
I think knowing it's a generator is super important. Right?
[00:59:44] Average Gary:
Yeah.
[00:59:45] Unknown:
Now groups are interesting because you actually have operations that all they do is is permute the group, is change the order around the group. It's like you have operations that just change the order around. It's like shuffle is the operation. And it has closure. Right? It has associativity. It has Yeah. It's like it has all of it. It has all of it. And then, oh, but all it does is change the order. It's really fucking cool.
[01:00:12] Average Gary:
Alright. We are at the top of the hour here. We didn't hit boost either. We're only a couple. Can we hit them? Yeah. Let's say of course, we gotta hit the boost. You got them up or you want me to pull them up? I have them up. I can let me share the screen. I got you, fam. Share away. Thank you to everybody at boost before we read them.
[01:00:33] Unknown:
Thank you to everyone who boosts and listens. You know, I I I noticed that it's starting to slow down and I that's is what I expect. I was, I was at my mechanics this morning who is actually one of the boosters today. Shout out. Shout out God's death who says thank you, gentlemen. But he was, you know, like, he was telling me, like, yeah, dude. It's getting it's just it's just hard. Like, it's just hard to really listen to this a lot. And I think we were saying this last week. Like, it's kinda diff. Like, take it slow, you know, take it slow. Take it as slow as you need, but try to get try to get through it. I think there's some cheese on it. Copy of the PDF too.
[01:01:14] Average Gary:
Give it a peek.
[01:01:16] Unknown:
Yeah. So, I'll hit Dan. Our boy Dan says, another great session. A lot of new terms for me to learn. My hope is that fundamentals and Average Gary will continue to discuss certain areas, terms, etcetera, about mathematics. I'll continue to listen to each episode individually as they come out. When the podcast hits 5 episodes, I'll plan to listen through again and take notes so that I can better understand the concepts discussed. Great advice. And similar to my approach to reading a textbook, fast and rough the first time through. 2nd time through is slower and precise.
Thanks again, gentlemen. Please keep it up. Thank you, Dan. Yeah. Thank you. You're the man, and that is great great advice. And I just would say do what you can. You know? That that like, you will benefit from struggling through this. Do what you can.
[01:02:12] Average Gary:
We got a abacus emoji boost from at John
[01:02:16] Unknown:
21 100 sats. Thank you, John. Thank you, John. Thank you. Your support means everything. Thank you, bud. We hit God's death. Thank you, gentlemen, and thank you for fixing my brakes this morning.
[01:02:30] Average Gary:
And, Pies with, I think it's Pies. Pies. Pies beer, mushroom, strong-arm emojis. So,
[01:02:39] Unknown:
cheers to you. And Proud to be proud to be, one another one of the shows, Pies Boots. Pies Boots is a lot of shows. Right? But not all of them. And, you know, we love you, man. I would love to hear, Pies. Love to hear from you some just how's it going? That's all.
[01:02:59] Average Gary:
Yeah. Especially if you made it this far into the episode. So thank you to anyone that has, and, pick up a copy of the PDF.
[01:03:09] Unknown:
Yeah. And I'll continue to I'll continue to add resources to the show notes. I think their aftermath is a great idea, but I'll continue to look for other resources and add them to the show notes just for Be be on the lookout for some some,
[01:03:23] Average Gary:
some actual live sessions where we can do the math, not just talk about the math because there is a a visual element to this. We're visual creatures. And I think it is important to sort of go through the iterations of writing this stuff down and and proving it, by writing it down. But thank you for sharing another hour of your beautiful day with me. Absolutely. And thank every thank you guys for hanging in.
So, yes, I was going through the AES chapter, the understanding cryptography PDF. And it got to the point where it's, like, talking about the different layers and everything like that, but this is beyond, like, the math section.
[00:00:12] Unknown:
Yeah. I don't think that well, from my from my standpoint, I'm like trying to bring I'm I'm on the math side of this. Mhmm. You're so I would ignore almost all of the implementations of current, you know, current crypto systems that don't, you know, I think if you like, I defer that to you. You are the you are the cryptography side, and then you would be asking, you know, what is this, you know, what is the relevance, What's the mathematical relevance behind x y z? And at the moment, I probably have a hard would have a hard time. I don't remember AES. RSA is something that has an obvious,
[00:00:53] Average Gary:
obvious relevance because of modular arithmetic and discrete logarithms are such a Well, that's the public private key cryptography thing. Right? So, like, the AES is a symmetric cipher, and it's also a block slash stream cipher, like, combo thing. But, like, the block and stream cipher piece of that is I don't wanna say irrelevant to the public private key cryptography, but it's it's different considerations. Right? Like, it's good to understand those groups and everything like that and, like, those those basic math things. But when you were looking at, like, elliptic curve cryptography, I think it is distinctly different than, like, a stream cipher.
Right? Like, it they're 2 different things.
[00:01:35] Unknown:
And elliptic curve cryptography helps answer it actually would help answer the question of why the math is important. The implement these implementations are more, I think, to understand the general, just this general idea that you have a party that wants to encode plain text into ciphertext and wants it to be decoded without, you know, without attacks. So, like, I think that is like a very basic level of cryptography and, you know, you have the linear transformations and the affine transformations, like the old Caesar cipher to go through some of that. So from I would say, like, those are kind of interest those are useful in showing why modular arithmetic just matters for at the most basic level. Yeah. I am I am on this I am on this revelation kick, and I just posted it out of the motivate the math Noster account that I cannot understate the importance of modular arithmetic. And when I say the importance of it, like, 2 things. 1, for people like us, it's just it's just over and over again becoming as good with it as we did with multiplication and addition. Mhmm. Internalizing it because there's no it's, a, it's so powerful and it's such a big part of why crypto why the cryptography we use works, but, b, it's it's needed. It's just it's substrate. It's total total substrate for it.
And I have you know, I'm like 2 years into my rabbit hole on this. And, God, I wish I brought my notebook down to show you on screen. Just the mountains and mountains of modular arithmetic I've done just in notebooks where I'll sit somewhere where I'm going to wait for like a couple hours. And remember the exercise I did last week when I was talking about a cyclic group where I was saying, oh, it's 2 you'd start taking the powers. Mhmm. 2 oh, by the way, we do have we I have smaller rata, and this is one of them. But, you know, you take 2 to the first power, 2 to the second power, 2 to the 3rd, and then you keep so, like, I have these notebooks where I I go all the way up the prime numbers up to as far as I can. It's just as far as I can. So I'll have a prime number like 53 and I'm testing every single number to see if it generates like the group 0 through 52. I like Oh, wow.
Like that is Yeah. Yeah. The level at which I that I am trying to internalize this, and I can see it. Every couple of weeks or so, I can just see I'm getting better, faster, more adept. You know, it's like Yeah. You learn it's like learning a lay up and then you learn how to take a little hook shot and you learn how to take a jump shot and eventually, you know, the more you do it the more the better you get at it. Right. And then it because what you know, then I go through then we decide to do this podcast. Right? And as you guys know, I'm not a math PhD. Right? I only just started learning stuff 2 years ago for the most part. Mhmm. And I have this book written by Neil Kablets that is modem that that called it's called a course in number theory and cryptography, and it's a graduate text. But it is the thing I've been going through to see now where, you know, where is math being used in cryptography because this is a math book for cryptography.
And, I have to tell you, like, going through that book now versus going through the understanding cryptography book 2 years ago, it's like a different story. It's like I've leveled up like 50 times. And a lot of it is I can tell you a lot of it is the work I did just sitting down doing arithmetic. And when I say, you know, we say modular arithmetic, it's like, yeah, you take you find an n that you want to have mod and you just play you find you you take any number and try to find the inverse. Right? That's a great exercise right there. So let's say you have mod 11, and you want to take the inverse of the number 2. You want to take And what do you mean by the inverse? What what does that mean? Inverse is, remember, like dividing.
Right? And in abstract algebra, you remember we had the we had those 4 axioms where there existed an identity element, and then there exists an inverse. Yeah. Yeah. It's you to the identity element. Yep. So in multiplication, and a lot of times I'm assuming multiplication without saying it, and that's where I got in a little I think purists purists are going to be angry about how I talked about cyclic groups last week because I just assumed multiplication. But like in multiplication, your identity element is 1. And so you want to say, I have an element that I want to find the inverse of, so I have an element like 2. What what number should I multiply by 2 in model 11, right, that the answer would be 1?
[00:06:38] Average Gary:
Now listen to Hold on. Say that one more time.
[00:06:41] Unknown:
So what number multiplies 2 that gives me an answer of 1 Model 11? There's only 10 possible choices. Right? Is it yeah. Hold on. So yeah. I'll sit with it for literally, sit with it for a second. Start cycling through. I think it's almost I think it's 6. It is 6. That's right. Yeah. Right? So so just for to verbalize it for the transcript, 2 times 6 is 12 which in mod 11 is 1. So that means that 6 is the inverse of 2. Meaning, when when you wanna divide 2 by 6 in the space, like, basically in the finite field mod 11 Yeah. You're actually well, it's not it's actually 2 times 6.
Dividing is Is 1. Yeah. Dividing is multiplication. And it's funny, on on, Rock Paper Bitcoin, which hasn't dropped yet, I had a whole thing about all the new podcasts I was doing. And I was told a story about my grandmother telling me that, love does not divide. It multiplies. And finite fields are like that too. You're actually Okay. So that you're multiplying to divide.
[00:07:54] Average Gary:
Yeah. It's like Columbus going east to go west.
[00:07:58] Unknown:
The inverse is What? Other way around.
[00:08:03] Average Gary:
The element times the element to the power of negative one Well, hold on.
[00:08:09] Unknown:
Equals 1, though. Let's just take our normal arithmetic. Right? If I have one of the inverse of 2 in, like, the real number system, then the answer is 1 half. No. That's for under addition. Sorry. Under addition is negative 2. Under multiplication. Oh, yep. Okay. So under multiplication, it'd be 1 half. Right? Because that's the number I multiply by 2 in the number system I'm in to get 1. But if I'm in the number system, which is basically it's called it's called the quotient group of the integers, model 11, let's just say, which is my now it's which is a set of numbers. Why is it a quotient group? Quotient is the It's it's just the name of it. Well, it it's called the quotient group. And in this case, z divided by 11 z.
[00:08:59] Average Gary:
Right. Yeah. Because quotient is the term for the answer of division. Right?
[00:09:05] Unknown:
That's it is term. Yes. It's term and division. I wouldn't think too hard about it right now. I would focus on the the group we're so the set of numbers we're now in. Right? Mhmm. 0 through 10. Right? And in that set of numbers with those with with the operational multiplication in this, right, in this quote unquote group.
[00:09:29] Average Gary:
Mhmm.
[00:09:32] Unknown:
If I have the number 2 as a member of my group. Right? And the number 1 is a member of my group. But what's the number number 1 is a very special member of my group. It's called the identity element of my group. And so I want another special member. There's another member of my group called the inverse that I know if I multiply by 2, I get the answer of 1. And you just figured out earlier that that number is 6.
[00:09:58] Average Gary:
And the, let me let me try to think of this. The inverse though but this is strictly speaking though for a quotient group, meaning a group based on the operation of multiplication.
[00:10:13] Unknown:
Well, now is that inflate don't I would not inflate the name. If I'm almost sorry I said it. Okay. Oh, it's alright I said the name. For the group that we're in, which is this finite field model, and it's like model 11 Mhmm. Which consists of the elements 0 through 10, not the numbers that integer 0, 1, 2, 3, 4, 5, 3, 10. Right.
[00:10:35] Average Gary:
Right? Now is there any relation between the identity element and this inverse or is it is one always used as the inverse?
[00:10:48] Unknown:
Well, the one the number one is always the identity element if the operation is multiplication.
[00:10:55] Average Gary:
Okay. Yeah.
[00:10:57] Unknown:
Someone's gonna correct me on that one. I'm sure. For that for math, I haven't studied yet. But, like, that's generally what we could say to ourselves.
[00:11:06] Average Gary:
Because one times an element is itself. Yeah. That's right. Right. So
[00:11:13] Unknown:
the inverse is always the number that multiplies an element of the group to get back to 1.
[00:11:21] Average Gary:
Okay.
[00:11:22] Unknown:
And it doesn't always exist. Right? So then you don't have a group. But, like so in other words, for example, you can't divide by, like, you can't divide by 0.
[00:11:35] Average Gary:
Right.
[00:11:36] Unknown:
It doesn't you know, there's not there doesn't always exist an inverse. Then that's the difference between, say, a ring and a field, not that we haven't gotten into that yet. But a field is has is restricted in a lot of different ways. One of which is that an inverse it's called an integral domain and that there always is a number. There's always there always exists an inverse. I I think I could be screwing this up. But I'm pretty sure that's the case. And and that's the case in in what context, though? Right?
[00:12:08] Average Gary:
So there is what do you mean? Like, is that the case in certain
[00:12:17] Unknown:
groups or certain fields? Definitely certain groups but of I believe all anything called a field, there are certainly at least a finite field. Mhmm. So and this is some any at least a finite field is always going to have, I believe it's always gonna have an inverse element.
[00:12:37] Average Gary:
Well, because a finite field is defined by modular arithmetic.
[00:12:41] Unknown:
Well, yes. But really it's see this I started talking about this last week. There's this there's this chain. Okay? It starts with starts with defining a ring, which is a variant it's like a variant idea of a group where that there's 2 operations instead of 1. They're both defined. 1 is definitely addition and the other is definitely multiplication. Right? And in the most general version of what you call a ring, the group axioms are true for addition but not multiplication. Okay? So you have like you have all 4 group axioms for addition, but for multiplication you only have closure and associativity.
You certainly don't have necessarily unity or what's called like the number one doesn't necessarily exist. So there's a ring called the ring with unity where it does exist. And then there's something called the commutative ring where, A times B equals B times A. That property exists. But that's not necessarily it's kind of like remember when we said groups don't have to be abelian? Groups don't have to we define an abelian group that's commutative on the operation, meaning from a left rightness perspective, A operates on B is the same as B operating on A. So basic groups are not necessarily commutated, but they can be.
Rings are always commutated for the addition operation, but not necessarily multiplication. You have to specify that that's the type of ring you're working with. And how is that specified then? You call it a ring with, a commutative ring. Right. So you say now I'm specifying that I have a commutative ring because the most general version of a ring is not necessarily
[00:14:33] Average Gary:
community. Okay. Alright. And you're just saying the when you specify that, you're just meaning that this ring has this additional property. Yes. And then there's a chain
[00:14:44] Unknown:
of properties that if they're all met, you actually you have a field. Mhmm. So you have a very specific version of a ring. It's kind of like you have you ask everyone in a room, say You're all rings, and everybody raise your hand. And then you say, how many of you are commutator? And then a bunch of hands go down. And then you say, how many of you have the unity element? And a bunch of hands go down. Then you say, how many of you where, if I have 2 numbers multiplying equal to 0, one of them has to be 0. Right? A bunch of hands go down, and then you continue this process. And at the end of the line, you get you say, you sir are a field.
Everyone else is still is a ring. Everyone in the room's a ring, but you sir, who meets all of these, there's probably in the book that I sent you the picture of, there were 6 different, variations of what a ring is or restrictions.
[00:15:45] Average Gary:
Now are these rings used for different purposes? And I'm assuming that well, let me not say. I'm assuming are are there different purposes for these rings, but then do we only care about the rings that are fields for cryptography?
[00:16:00] Unknown:
Yeah. I think what we care that they're rings so that the that the like, I had this cop out statement yesterday. We could do, like, magical math if we know something's a group. And if we know something's a ring, we can really work with it in a powerful way. Mhmm. We own so we work with fields. Okay? But they the fact that certain things are rings is important. And I don't wanna get pedantic about it. But, like, here here's an example. Okay. So a lot of times with rings, you look at polynomials. Should I not take advantage should I not assume we know what a polynomial No. Let's not assume what a polynomial is. So a polynomial is something, you know, we learned about in, probably middle school that is like, ax squared plus bx plus c is an example of a polynomial.
It's an order of 2 polynomial. Right. The polynomials of the form some, a k a sub k times x to the k plus, so in other words, some some some actual number times x to some power. Right. Right? Plus another number times x to one lower power, dot dot dot down the line,
[00:17:30] Average Gary:
some factor some number times x plus some other number. So in other words I think the most like the This is hard to explain. This is easier to If we put it in a bitcoin let's put it in a bitcoin context. Right? There's this the the equation, the polynomial equation that describes the secp256k1 curve that is used in bitcoin is y squared equals x cubed plus 7.
[00:17:54] Unknown:
Yep. So that is an example of That's a polynomial. Yes. But the most beautiful example of a polynomial actually is an act is a digit itself. So like in base in the base ten number system, you know, any every number is actually a polynomial because, so like for example, the number 256 is 2 times 10 squared plus 5 times 10 plus 6. So, like, the numbers themselves and that's why when I say it matters that we know they're rings because the numbers that are actually going into this thing are polynomials and we know polynomials are can be rings.
And it actually is why we can do all this. It's one of the reasons. It's pretty fucking cool when you when it unpacks. But a number itself is a base base something polynomial. Right? Right. A binary number, right, is a is so the coefficients right? So you have so in a polynomial of coefficients, which is like the did the digits were 2, 5, and 6. Those were the coefficients. 2, 5, and 6 were the coefficients, and the x's were the base, 10 squared plus 10. Yeah. And so you see this in base 2 the same way. Right? The number 111 is, you know, 2 squared plus 2 plus 1 which is 7. Right? Number 111 in base 2. If you I took f f in x. Right? Yep. That's 250 that's 16.
That that, you know, right? That's, 16 times 16 plus 16. Plus 15. I'm sorry. Plus 15. So it's 15 times 16 plus 50. So all of the numbers are polynomials. Right?
[00:19:47] Average Gary:
Yeah. It just depends on what base you have. In a certain base. Right? This makes sense again in the AES section of the of the understanding cryptography book. It goes into saying, it was trying to represent I can't remember the exact terminology. It was trying to represent this numerical value, but it wanted to use modular arithmetic. But the problem was it what did not have a prime for the mod number. Right. And so, what they did was they used the the Galloi or the Galois field of base 2 and they converted the numbers to a Galois field of base 2 representing a polynomial.
It was more of it used 8 bits so eight sets of, ones and zeros, which had some implication on, like, the hardware and software side. But then the different aspects of the polynomials, you would the coefficients were the ones or the zeros. So in the example that you just said where it's like 111 is actually 7 the 111 representation of this group that was being represented was actually X squared x plus x plus 1. Yeah. And if you did 10011001 so just put a one at the front and the end of the 8 bits and then 2 ones in the center That turns into x to the 7th. Yeah.
And then You're dropping my memory now. It was It would be x to the 6th, but that's time 0. So you just nullify it, drop it. It would be x to the 5th, but you nullify drop it because it's multiplying by 0. So x to the 7th plus x to the 4th plus x to the 3rd. Right? So you have that first one, which is x to the 7th, and then the x to the 4th or the 3rd. You drop the next 2 plus 1, and so the final result of whatever that number is. And it it was just a way, I think, of, like, taking a group without, like, a prime modulus and applying something over it that does because 2 is a prime number.
That's right. You you're able to have these properties of a a Galois field.
[00:22:10] Unknown:
Yeah. And 2 is prime to every odd number. Right? So that's the other that's the other one. We haven't gotten to this yet because I haven't gotten in any numbers. Yeah. But, like, the idea of a number being prime to another number has to do with this concept called greatest common divisor. It's really important and it's this goes have you you've ever, you know, you hear me all the time, Gary, when I'm talking to you and texting you, going through saying these words, division algorithm, Euclidean algorithm Yep. Greatest common divisor, congruence, modular arithmetic. This package of things is, really where the sauce is at.
And And the Euclidean algorithm was what I reviewed last night. Right. And so the Euclidean algorithm is the way to find the greatest common divisor, not to get too not to get too cute right now, but I only recently discovered from this Caballus book that it's how you also get the inverse element of like when you can't just multiply 2 and 6 in your head and know that that's 1 more than 11. When you say you can't because you're dealing with large prime numbers. Yeah. I'm telling you what find find the inverse of, you know, 722 mod, you know, some prime number that's 5 digits long.
It's like you're not gonna do it without there's just no way. You can't even sit with a calculator long enough to test all those numbers out. Right? And the Euclidean the Euclidean algorithm, we will we will spend time on this. I promise.
[00:23:42] Average Gary:
Mhmm.
[00:23:44] Unknown:
It's so powerful because you can a, find the greatest common what it does is find the greatest common divisor between two numbers. Mhmm. But, it leverages something called Bayesout's identity where now you have you also it means that the greatest common divisor is also a linear combination of the two numbers, which meaning like if I have two numbers, any two numbers, then we'll we'll use small ones like 57. Right? We know the greatest common divisor of 57 is 1, which actually means that they're prime to each other, meaning they have no common factors. K? Right. I can also say that 1 equals a linear combination of 57, meaning I can take any two numbers x and y and multiply 7 x plus 5 plus 5 y. I can always find a combination that equals 1.
[00:24:40] Average Gary:
Alright. Hold on. Let's unpack that. The you said it's a linear combination. Yes. Which is The linear combination means and is it linear because you're taking an x and a y and that that implies a point on a plane? Yeah.
[00:24:56] Unknown:
And it's also one dimension because you're just multiplying by 1 like, pow to the power of 1 variables. Right. Right. Right. So it's just that's that's what linear means. Linear means you're multiplying by an x to the one power. Whereas, if you're multiplying by some if you have a a polynomial that goes up to x squared, that's considered quadratic. X cubed is considered cubic. So back to the greatest common divisor being 1, say of 7 and 5, and I can always make a combination 7x+5y equals 1. And in my head, I can tell you if y is 3 and x is negative 2, that that does it.
But Yeah. Right? So if we just slow down at negative 14 plus 15 is 1. But I know because of Bezout's identity and the Euclidean algorithm, I know I can find the linear combination. I'm gonna do, like, a lot of problems. I'm working on getting set up to do this. It's really powerful. And the fact is, it's what's important to know is that you can do that even when the numbers are just so big beyond your reach. And that's why that's why, like, these little ingredients matter. Is so that you have absolute confidence that you're doing the right thing, even though there's no way you can confirm in your head that you're doing the right thing. Like when you when you're taking 3 digit numbers to the power of another 3 digit number and you're you're actually doing it.
You you don't even have a calculator that you or Excel. There's nothing. There's literally nothing where you can visually verify you're doing the right thing. You you must be able to rely on the math. You must know. The properties of the underlying math. You must. Yes. And because it's the only way. Right? You're it's like you learn how things work on earth and you go into outer space and you go do it and you without without the benefit of gravity and you have to know you're doing the right thing.
[00:27:03] Average Gary:
Yeah. I mean, I I think that like that in and of itself right there is like the reason to motivate the math. Right? It's because if you cannot understand these properties, if you don't if you've not built the context around this to understand what, what do you say, linear combination
[00:27:18] Unknown:
Yeah. And I'm sorry sometimes with the with the with the terminology. In my brain, it thinks it's helpful to say these things, but No. No. It is it is because it's It's confusing, but, like, these are linear combination is something I would just say people should know what it is. It's something it's a term people throw around very, very loosely.
[00:27:36] Average Gary:
Remind me though why in in what context is the linear combination
[00:27:41] Unknown:
applicable and relevant though. Right? Yeah. Okay. So, I mean, any kind of mathematical model. So, y equals mx plus b is a linear was a linear combination. Right? Okay. Yeah. It's a very simple one. But, like, when you try to, you wanna be a chart boy and you wanna say, oh, you know, this is a this is, that something has a mathematical relationship. Like, for example, you wanna model the price of a home, and you've got, you've got a few variables of data. Right? And you wanna decide which ones matter. So what you have is price of similar homes in the area. You have maybe interest rates and you have, give the price of Bitcoin.
You have many things. And then what you'll do is you'll create a linear combination of those things so that you can make your model to predict, like, say, to predict the price of a home. Right? Mhmm. It's gonna be some number times prevailing rate, some number times the price of Bitcoin, some number times the price of gold. Some number times the average median price in the area. And then you would have these statistical things that tell you whether or not those variables actually do matter. Is it because you sort of need, like, a basis
[00:29:01] Average Gary:
starting point for your chart or whatever because that one value is now where you can, like, start from.
[00:29:08] Unknown:
Well, yeah. It's it's bay it's like if you wanna say you wanna determine the value of something Mhmm. And say it's a it's based on the value of other things.
[00:29:18] Average Gary:
Yeah. Yeah. Yeah.
[00:29:19] Unknown:
I'm all I'm saying is a simp the simplest way to do that is what's called the linear combination of those things where you just you don't do anything to those numbers. You don't say, oh, I have to square the price of Bitcoin. Right. I'm just gonna multiply it by these things, x y z. And that's a linear combination. Okay. It's a linear combination. Exactly. And, you know, it's it's a very basic concept. It's probably worth Googling. And, you know, that it that's, it's very that's another one that's like congruence. Like, it's you just wanna know what it means. You know, I talked about I I talked about on Rock Paper Bitcoin. I think it's the one that you called me after to start this podcast when I talked about this term, morphogenal divergence.
Yep. Okay. So what that was all about was that, knowing whether it's like you have one you got one system that's like a linear combination. And let's just say, you know, in a system, you have a set of information that's absolutely a function of the other information that's in the space. Like, it adds no new information.
[00:30:38] Average Gary:
Right?
[00:30:39] Unknown:
So even though that linear it's like a it's a different it's kind of like, you know, you have these chart boys that add no value because their actual their models are are essentially giving no additional information to It's all deriving from the same context. What's already out there. Yeah. And so linear algebra, the field, right, is very much the you know, it's a way to look at essentially the value of new information coming from a from linear combinations in systems. And this is really like, I'm really feeling uncomfortable with this these explanations. We're good. We're good. Yeah. I don't think they're very good, but We can go back to cryptography.
[00:31:23] Average Gary:
We've said, Chart Boy wait one too many times.
[00:31:27] Unknown:
Yeah. When I say Chart Boy, you're you that should be a signal that I'm about to shit on the math there. Right? Okay. And the significance. But, like, well so crypto so here's the other thing, though, that's related that's here's where it's relevant to cryptography or cryptol I should say cryptology. Right? And there's a is there a difference between cryptology
[00:31:51] Average Gary:
and cryptography? I remember it being broken down because there's cryptanalysis and some other things, and I can't recall the the delineation or the demarcations.
[00:32:00] Unknown:
Maybe we don't care what the definitions are, but the idea the fur like, when you like in this Cobblets book, first page of the book, it talks about, okay. So there's a shift, like a shift cipher where Right. I pick a number between 0 26 and I'm gonna use my I'm gonna code it mod 20 I'm gonna code my my, my crypto tech my ciphertext is gonna be just mod a modded version, a shifted version of my plain text. Right? And so what, you know, what's immediately so after you realize how kind of cool that is, right, they immediately tell you, oh, by the way, anyone can see the most popular letter in the English language, e. So they can use, you know, they can use that to figure out what your most frequent letter is. Right. And then easily back into the, and if they can't figure it out from the letter e, they can add a second letter t.
Right? Every So so forth. And the the but these are these actually are linear these are linear, did I call them linear combinations. Right? Yeah. Yeah. So and they're linear they're they're congruences. In other words, the difference between a congruence and an equality is you might say a x plus b y equals c, but you can say a x plus b y is congruent to c mod 11. See, in the mod in the mod space, it's called congruent because there is not a unique answer. They're trying to they're just trying to say, well, you know, in mod 11, 0, 11, 22, 33, 44 are all the same number.
So that we talk the the terminology is congruent. So when I talk right? I talk about congruence as like the most important thing in module. Modular arithmetic and congruence are like addition, subtraction, and equations. Congruence is a type of equation where we're talking where we're dealing with remainders, right, in mod space.
[00:34:09] Average Gary:
Okay. Because because it okay. I'm sorry if that wasn't clear. No. That's good. And that's a triple line. Right? Yes. That's what that's like 3 lines instead of 2. Ah, okay. Alright. That makes a lot more sense because I've seen that in the text. And now I can put a word to what that means. Because in my mind, I'm like triple equals and that's incorrect, though. That's incorrect. Heck is this triple equal? It's because the idea of equality doesn't necessarily apply to these modular arithmetic
[00:34:38] Unknown:
fields or groups. Right? That's right. Because equality means there's a unique answer. You know? I'm sure I'll get corrected on that. Okay. Equality usually means there's a unique answer. Congruence is just means that they're you're right. It's like you can see there's other areas there's other examples of congruence in mathematics. Right? Like congruent triangles, they don't have the same sides, but they have the same angles.
[00:35:05] Average Gary:
Right? Okay. Yeah. Yeah. Yeah.
[00:35:07] Unknown:
So we missed yeah.
[00:35:09] Average Gary:
What and I was thinking about our example of mod 11 and how we were talking about that. We did, like, the, what was the inverse of 2, which was which was, 6. Yeah. Right? And I was thinking about, like, if you're if you're if you're working within a group, like of addition mod of, an addition group of mod 11 and 2+ 14. Right? In regular base 10, regular arithmetic equals 16. But in this mod Mhmm. It's a different answer and the the outcome is not like, there's no equality in what those outcomes are, but there's congruence when you're modding. Yeah. Because the numerical representation let me what so let's see. What 2 +14, so 16 mod 11 is 5. Right?
So, like, 2 is not equal to 5. Like, that that is not equal, but it 2 is congruent to 5 when used within this modulo
[00:36:13] Unknown:
11 context or group. Yeah. I think a great way to go, you just jogged a memory of is to go back to clock math. Right? Yeah. 3 o'clock is congruent to 3 o'clock, but doesn't mean it's equal because it could be on a different day.
[00:36:27] Average Gary:
Right? Yeah. Yep. That's very true. Or it could be 3 AM versus 3 PM sort of thing.
[00:36:33] Unknown:
But you you you see the point is that there's not equal is very restrictive. Yeah. So and again, I'm gonna motivate here and I'm gonna regret introducing another confusing term. But there is and there is something called an equivalence relationship that congruence satisfies. Relationship is something that has 3 properties that you will all understand. 1 is it's called reflexive meaning like a equals a. Okay. Shout out Ayn Rand, you know? So like if your thing equals your thing, right, if if that, you know, it's that's kind of a trivial example but it's not always the case. So that's the first like that's the first quality.
The second is it has to be symmetric meaning like a equals b means that b equals a and vice versa. So if a equals b means b equals a, then you have equivalent. It's another property of equivalence. And the last property is called the transitor property, Meaning if a equals b and b equals c, then a equals c.
[00:37:42] Average Gary:
Yep. You lost me.
[00:37:44] Unknown:
So oh, well, okay. If I have, the trans that's what the transitor property means. So if I have two numbers, a, b, and c three numbers, a, b, and c. Okay. Yeah. Yeah. Yeah. Right. It's so in other words, if the equality extends, if the equivalence extends, it's what then you have what's called an equivalence relationship if those three properties are satisfied. In other words, have you ever asked the question what does equal even fucking mean?
[00:38:10] Average Gary:
I mean, I have lately when I when I saw the congruence symbol.
[00:38:16] Unknown:
Yeah. So, I mean, there is a notion of equal. It probably in, like, God's world. See, there's probably this notion of, like, well, when a cell divides, it makes a copy. Maybe it's an exact copy. That's a I'm sure there's like, there are things in nature that are equal. Right? Even though we're told there's no such thing. Right?
[00:38:40] Average Gary:
The the there's like a there's a, what is it? Like, Newton's law of, like, every force has an equal and opposite force or reaction. Every action has an equal and opposite reaction sort of thing. Like, there's some sort of equality in that. I mean, like my skeletal structure is in I wouldn't even say is equal, but, like, my body composition is equal to the gravitational force on this planet. Maybe. See, and that's yeah. That's not even that's not even, like, an exact
[00:39:20] Unknown:
thing. Very challenging. It's very challenging to sit here and define equal. Right. So this is my little pet answer to people when they ask things like was math discovered or invented? Because I think that like there are certain concepts God gave us and like the fact that two things could be the same is a concept, but we have no formal way of knowing. So when we define this formal structure to say if 2 things are, we don't even say equal because that's like too, presumptive, but we would call it an equivalence relationship. Mhmm. Right?
That something satisfies an equivalence relationship if reflexiveness, symmetry, and transitivity are basically present. Then you have an you can have an equivalent relationship. So, for example, the the greater than is not an equivalence relationship because it doesn't satisfy all 3 of them. K. Right? Like, it's certainly like if The reflective the reflects the reflective one is not satisfied there. And a greater than b is not that's right. But if a greater than or equal to b, it does.
[00:40:35] Average Gary:
Okay. Yeah.
[00:40:37] Unknown:
But that's because now you have you have you have equality in there. But yeah. So it's a good like, it's a good non example is a greater than b is not reflexive. Right? Mhmm. So therefore, non equivalent relationship. Now mod congruence modulo n is a congruent is a is an equivalence relationship and it's the abstract algebra route enables you to prove these things.
[00:41:07] Average Gary:
And it's an equivalence rate relationship because it has the reflexive and the transitive
[00:41:15] Unknown:
and a mod n equals a mod n. Yeah. Right? If a mod n equals b mod n which could be like 11 mod 11, 12, 22 mod 11, then 22 mod 11 equals 11 mod 11. Right? So it has that symmetry and then it has transitivity clearly. Well, if I have 11, 22, and 33, and 11 equals 22, 22 equals 33, sorry, congruent, then 11 is congruent to 33. That's true. Model well, model 11. Right? They're all equal to 0.
[00:41:48] Average Gary:
Okay. Okay.
[00:41:49] Unknown:
So you have what's called an equivalence relationship. And, so what I was saying before was, yeah, I actually think we like, I think God gave us some notion of, like, that 2 things are the same, but we had to like, that we had to invent. Like, man had to just invent the rules. Somebody I don't know who I don't know who did this. Mhmm. It's pretty it's quite an achievement in the human race, whoever formalized what an equivalence relationship is.
[00:42:22] Average Gary:
Well, because you're yeah. You're you're almost, and this is something I've had for a long time. A belief I've had for a long time is, like, the mathematics is the closest we've come to explaining, like, how our world works. It's the closest we come to the language of God because it's it's our best attempt at explaining what exists in this world and then the relationship between all of the properties of it. Right?
[00:42:51] Unknown:
Yeah. Yeah. And then and then so these acts these these, like, definitions, these axioms and being able to call something a group, a lot of it is really just so that you don't have to,
[00:43:03] Average Gary:
it's kind of being able to save your game. You know? It's like it's it's it's signal over noise. Like, you can focus on like, not not saying that everything else is noise, but, like, without having a lens to look through, without having a filter.
[00:43:19] Unknown:
You would have to prove these things over and over and over again every time you wanted to verify something. And so what these theorems and these proofs enable you to do is, like, it's kinda like save your game. Like, you know, you don't have to redo the whole level every single time Right. To do the thing you're trying to do. Right. Yeah. So you get to sit on the shoulders of what you verified in the past. And that's why that is why when I I that's why I say so completely division algorithm, Euclidean algorithm, Bayes' out to unity Yeah. Yeah.
[00:43:55] Average Gary:
Modular arithmetic and groups. When I see the the the Euclidean algorithm too, I I see that because it it is a pattern of reducing the steps to take to get the greatest common divisor Yeah. No matter how big your number is that you're starting or how big your two numbers are that you're starting with to find the greatest common divisor. But there But it's a division is a linear combination. That's that's the first thing. Right?
[00:44:20] Unknown:
Is that my my number So I have two numbers. Right? It, 57. Right? I say 7 equals 1 times 5 plus 2. That's a linear combination. Right? Of 5 and 2. 1 times 5 plus 1 times 2. Yeah. And then the Euclidean algorithm then takes the 5 and the 2 and does the same thing. Right? It says 5 equals 1 time 2 times 2 plus 1. Yeah. And then that's how you know, so this was this is, it's such a fine thought here. Right? Because we're we're covering we're on like a I feel like we're really surfing the wave and just it's the the line between wiping out and continuing in this conversation is very thin. You know? We're getting yeah. We're getting to that point.
[00:45:14] Average Gary:
But it's good. Like, I feel like we're, you know, I feel like we're actually saying something that matters. When I think anybody any like, my recommendation to try to, like, take it back to to where I was trying to grok this last night, and I think I even messaged you about it. It's like, I I think I even posted on Nasr or something about it. I was like, I needed to go back and learn what factoring was. Right? Like, what is what is prime factoring? Right? And it's this methodology. Like, that is the that is the thing that is the computation that you are making that you're simplifying using the Euclidean algorithm is this prime factorization. And all the prime factorization is is you start with the smallest prime number, which is 2 or or 1. Right? And if 1 is is the only one, and you divide the number that you're factoring by 2.
And then you take that, and if there's no, oh, shoot. What is it? If there is if there's no remainder, then you go to the next prime number. If there is a remainder, you continue
[00:46:16] Unknown:
to divide by 2. Yeah. And so this is again, this is why really the first topic to start with is prime numbers. Yeah. Because that is the atom. Right? Like, that's the atom. That's the smallest unit of of all of this. Right? Everything is is And, you know, every number is some product of primes. Right? And then every number is a unique product, just like every number is a linear combination of its base. Right? Every number is also a product of primes. Right. Right? And that, you can you can and it's unique. Like, it's a unique product of primes that all you can do is change the order, but you can't change the primes.
[00:47:08] Average Gary:
Yeah. Right?
[00:47:09] Unknown:
And that becomes really that becomes really important. It's so incredible what you end up, it's just so incredible what you end up getting. I haven't by the way, I haven't done my Roddy
[00:47:24] Average Gary:
yet. I I I Well, let me let me take the let me take the audience briefly through factoring the number 84 Cool. Because I because I did that. And, and the prime factorization of 84, you get to 2 times 3 times 2 times 2 times 3 times 7. And, the way you get there is you start with the smallest prime, which is 2. You do 84 divided by 2, which is 42. Right? So okay. So there's no remainder. So we continue with 2 being the divisor. So we take 42 divided by 2, which is 21. So then the 2 times 2, and now you got 21 left. Yep. And but now we can't divide 21 by 2 without having a remainder. Mhmm. Right? So now because there's a remainder, we we switch it up, and we we go to the next prime number, which is 3 or the next highest prime number, which is 3. So and then 21 divided by 3 is 7.
You try to do 7 divided by 3, you end with the remainder. So you can't do that. And it just leads you from 3 to 5. You can't again. No. There's a remainder there. It doesn't work. You go back up to 7. We're right back at where we're at, 7 and 7. So it becomes 2 times 2 times 3 times 7. Yep. And that's the prime factor prime factorization of the number 84 using base 10.
[00:48:55] Unknown:
Yeah. So, you know, we'll get to discrete logarithms,
[00:49:00] Average Gary:
which are No. No. No. No. No. Don't. Don't. We're gonna crash on the wave if you just don't even go there. The the reason I wanted to go through this exercise because the prime factorization so we just prime factored 84. Right? 2,237.
[00:49:13] Unknown:
The budget is not supposed to be able to do it by hand so easy. That's the key. That that's Well,
[00:49:18] Average Gary:
with smaller numbers, you can. Right? But I guess what I would point out is 84 is always
[00:49:23] Unknown:
the product of those 3. Really, I'd say those three numbers. 2 squared, so 2 squared, 3 to the 1, 7 to the 1. So it's always a right? It's always a it's always a multiplication of some prime to a power. Mhmm. And it's so for 84, it's always those those three numbers to those three powers. 2 squared, 3 to the 1, 7 to the 1. And no matter what no matter what universe you end up in, it's always going to be those 3. It could now that you could do it in different orders.
[00:49:58] Average Gary:
Right? Right. But to tee up, I guess, maybe the Euclidean algorithm, like, how do you get that? So so we have 84. We figured we private factored that. Finding the greatest common divisor greatest common divisor of 84 and another number, you have to factor that other number. Like 35 for example. Well, in my notes here, it's 30. So Okay. We can go off of that so I can read it. Okay. That works. 30 works. Right. But it's it's so so we've already done the the 80. 84. So now we do 30. So 30 divided by 2 gives us 15. Right? So 2 is the first factor prime factor there.
When we do 15 divided by 2, it doesn't work because we have a remainder. So we have to go to 3. 15 divided by 3 gives us 5. We're at a relatively small prime. So we could do 5 divided by 3, but there's a remainder, so that doesn't work. And we end up just back at 5 and 5, and so it becomes 2 to 2 to the first power times 3 to the first power times 5 to the first power. Mhmm. And so when you compare those numb you when you compare those prime factors, the greatest common divisitor ends up being the product of all the common prime factors.
[00:51:21] Unknown:
Mhmm. So 75 get excluded because Very much benefits visually, but, yeah, keep keep keep keep keep keep keep going. Well well, 5 is excluded because 84
[00:51:30] Average Gary:
does not have that as a prime factor. Right. 7 is excluded because 30 does not have 7 as a prime factor. See it. And so all you're left with is 23.
[00:51:40] Unknown:
Right. So the way again, state it again. On the left side, you have 2 squared times 3 times 7 and on the right side you have 2 to the 1 times 3 to the 1 times 5. So you have 2 to the 1 times 3 to the 1 is in common on both sides. Right. Right? Yep. So 6, that makes 6 your common divisor. And what were your two numbers again? 30 84. 84 and 30. Right. 30. And 6 clearly divides those and it clearly does divide those. And, you know, I would challenge the audience member to see if there's a bigger number that divides both of those. Yeah.
Alright. Now the other cool thing, just to call back, is that 6 is gonna be a linear you can all you can make 6 a linear combination of those two numbers, 30 84. Not gonna do it right now. Oh, yeah. I I am gonna do it right now. 30 times 3. Go ahead. 30 times 3 plus 84 times negative 1. That's 90 minus 84 is 6. Yeah. So Beysaut's identity always works and, it's killer. And it's even it's really powerful when the greatest common divisor is 1. So I'll just leave that. I'll leave it at that. That's a little nugget for next time. Yeah.
Can I hit 2 so can I hit, this these errata are actually relevant? They're not Yeah. Yeah. Yeah. Let's hit the errata.
[00:53:13] Average Gary:
Hit the errata Okay. And then we can wrap it. I want I wanted to cover
[00:53:18] Unknown:
I I immediately posted this to Nasser when I we stopped we stopped rolling last episode because I knew it was an issue. Binary we I talked about a binary operation in a group. Right? Mhmm. Let me I'll just tell you what the binary what it what it actually means. What binary operation means that I can take two numbers, perform an operation on them, and get one number. Again, this sounds so obvious but, like, addition satisfies a binary operation because I could take two numbers, 3+2, and get one number 5. Mhmm. I can do that with multiplication.
I can do that with, there are many operations I can do that with. So, again, that's just technically, that's the definition. I said something different. Okay. Okay. And the but and this is it's why it's binary. It takes 2 inputs. Mhmm. It returns 1. Computer science people probably can see why that matters. Right? Then the other one was we talked about a cyclic group. Mhmm. And I just talked about taking powers because, again, I assume the I assume the operation was multiplication when I said that. But in the operation of addition, you could add numbers and try to get a cyclic group. So in other words, one would generate a cyclic group the cyclic group of integers under addition because you actually, no. It's not true. You'd only it would one would give you the positive integers, basically, because you you continue to add by 1.
I used multiple. I used powers. Okay. There's something I can't I think is really cool about it though and I gave that example mod 5 and we we took 2 to all these powers and kept getting 1, 4, 3, 2, 1, 2, 3, 4, 3, 4. We kept getting 1, 2, 3, and 4 in different orders. Mhmm. And so something that gets done in cryptography is you take one of the generators and you multiply it by all the numbers in the group and what it does is it just changes the order of all the numbers in the group. It keeps all the numbers the same which changes the order. I just want to point that out. It's something that's really cool and it's something that actually gets it's something that makes certain cryptographic, systems work.
Hey. Because the plain text may be like crackable, maybe it's ordered in a certain way. Right? So like for example, this is why I asked you earlier if you knew what the knapsack problem was. I just learned about this today. Mhmm. But if you order everything in a certain way, the knapsack problem relies on a very specific structure where, each it's a sequence that always increases and every element is bigger than the sum of all the prior elements.
[00:56:24] Average Gary:
Mhmm. And
[00:56:26] Unknown:
you can crack that one very easy, but if you change the order around, it's no longer It's problematic. In absolute no no effing way. Okay. Right? And so when you have a group, then you can just multiply all the numbers by by the generator to flip you. And then you have a completely different order. You have a different order. You have all the same numbers, a different order. Right. And you can this is you'll see this with not with, number you know, you do this to numbers, which are products of primes. It's your power where you just change you know, again, the order the order can change around, but you still have the same product.
It's so this notion of a cyclic group and the generator is really important because it's something that actually gets done to flip the order around of the elements of a group to make it harder to crack. I believe you. So, like, the the the way it's ordered yeah. So maybe there's a version of it that's ordered in such a nice way that it's actually really easy
[00:57:33] Average Gary:
to To crack it. To encrypt.
[00:57:36] Unknown:
Right? But the the one that you're decrypting is ordered differently.
[00:57:40] Average Gary:
And it's, like, impossible without secret. Is that the asymmetry piece of it? Yeah. Oh, okay. Right? And so this was, what I'm referring to today was Ah, okay. So if you're using a public key to rearrange the ordering, you need the private key to put it back in the right order. That's right.
[00:58:02] Unknown:
So and and so this was, Diffie and Merkle, and I should tell you in the book, this system was cracked by Shamir whose name comes up a lot. He must be important. But
[00:58:14] Average Gary:
Yeah. I've heard of Shamir. He has a sharding thing for keys.
[00:58:19] Unknown:
I assume that's with a d. Right?
[00:58:22] Average Gary:
What? Sharding? Sharding. Oh, yeah. Not shart yes. With the d. Yeah. Shamir Shards. Secret Shares. For Shares?
[00:58:34] Unknown:
Yeah. Right. Well, so anyway, it was crack, but it's it was like, it really illuminated for me again how cyclic group with a generator can actually be used to take something that otherwise is orderly and very manageable and you wanna make it unmanageable by and just by flipping the order around.
[00:58:52] Average Gary:
Right. It's beaut and so you're saying having a way to reorder it. Yes.
[00:58:57] Unknown:
Yeah. I thought that was, like, a super beautiful thing. So, anyway, that's that's part of my errata. The binary operation is a cyclic group. Cyclic group could be any op it could be any operation. Okay. We usually will always talk about powers and multiplication just in general. That's, like, almost always how we use it.
[00:59:15] Average Gary:
And when you say
[00:59:17] Unknown:
use it, you mean in the application of The generator. Yeah. Generator all and, you know, because in the first of all, we're dealing in a a ring. Yeah. A field which is also a ring that is either addition or multiplication, and we'll usually be dealing with the multiplication.
[00:59:30] Average Gary:
Does this that that does that so that means picking your generator is important then?
[00:59:38] Unknown:
I think knowing it's a generator is super important. Right?
[00:59:44] Average Gary:
Yeah.
[00:59:45] Unknown:
Now groups are interesting because you actually have operations that all they do is is permute the group, is change the order around the group. It's like you have operations that just change the order around. It's like shuffle is the operation. And it has closure. Right? It has associativity. It has Yeah. It's like it has all of it. It has all of it. And then, oh, but all it does is change the order. It's really fucking cool.
[01:00:12] Average Gary:
Alright. We are at the top of the hour here. We didn't hit boost either. We're only a couple. Can we hit them? Yeah. Let's say of course, we gotta hit the boost. You got them up or you want me to pull them up? I have them up. I can let me share the screen. I got you, fam. Share away. Thank you to everybody at boost before we read them.
[01:00:33] Unknown:
Thank you to everyone who boosts and listens. You know, I I I noticed that it's starting to slow down and I that's is what I expect. I was, I was at my mechanics this morning who is actually one of the boosters today. Shout out. Shout out God's death who says thank you, gentlemen. But he was, you know, like, he was telling me, like, yeah, dude. It's getting it's just it's just hard. Like, it's just hard to really listen to this a lot. And I think we were saying this last week. Like, it's kinda diff. Like, take it slow, you know, take it slow. Take it as slow as you need, but try to get try to get through it. I think there's some cheese on it. Copy of the PDF too.
[01:01:14] Average Gary:
Give it a peek.
[01:01:16] Unknown:
Yeah. So, I'll hit Dan. Our boy Dan says, another great session. A lot of new terms for me to learn. My hope is that fundamentals and Average Gary will continue to discuss certain areas, terms, etcetera, about mathematics. I'll continue to listen to each episode individually as they come out. When the podcast hits 5 episodes, I'll plan to listen through again and take notes so that I can better understand the concepts discussed. Great advice. And similar to my approach to reading a textbook, fast and rough the first time through. 2nd time through is slower and precise.
Thanks again, gentlemen. Please keep it up. Thank you, Dan. Yeah. Thank you. You're the man, and that is great great advice. And I just would say do what you can. You know? That that like, you will benefit from struggling through this. Do what you can.
[01:02:12] Average Gary:
We got a abacus emoji boost from at John
[01:02:16] Unknown:
21 100 sats. Thank you, John. Thank you, John. Thank you. Your support means everything. Thank you, bud. We hit God's death. Thank you, gentlemen, and thank you for fixing my brakes this morning.
[01:02:30] Average Gary:
And, Pies with, I think it's Pies. Pies. Pies beer, mushroom, strong-arm emojis. So,
[01:02:39] Unknown:
cheers to you. And Proud to be proud to be, one another one of the shows, Pies Boots. Pies Boots is a lot of shows. Right? But not all of them. And, you know, we love you, man. I would love to hear, Pies. Love to hear from you some just how's it going? That's all.
[01:02:59] Average Gary:
Yeah. Especially if you made it this far into the episode. So thank you to anyone that has, and, pick up a copy of the PDF.
[01:03:09] Unknown:
Yeah. And I'll continue to I'll continue to add resources to the show notes. I think their aftermath is a great idea, but I'll continue to look for other resources and add them to the show notes just for Be be on the lookout for some some,
[01:03:23] Average Gary:
some actual live sessions where we can do the math, not just talk about the math because there is a a visual element to this. We're visual creatures. And I think it is important to sort of go through the iterations of writing this stuff down and and proving it, by writing it down. But thank you for sharing another hour of your beautiful day with me. Absolutely. And thank every thank you guys for hanging in.
Introduction to Cryptography Concepts
The Importance of Modular Arithmetic
Understanding Inverses in Modular Arithmetic
Exploring Rings and Fields
Galois Fields and Polynomial Representation
Linear Combinations and Their Applications
Equivalence Relationships in Mathematics
Prime Factorization and Greatest Common Divisors
Cyclic Groups and Cryptography
Listener Feedback and Closing Remarks
