2^173(mod5) = (2^4)^43 * 2^1 = 1^43 * 2^1 = 1 * 2 = 2
2^4(mod5) = 1 because 16(mod5) = 1
Fermat's Little Theorem
https://mathworld.wolfram.com/FermatsLittleTheorem.html
Euler's Function
https://en.wikipedia.org/wiki/Euler's_totient_function
Elliptic Curves: Point Addition
https://www.rareskills.io/post/elliptic-curves-finite-fields
Diffie-Hellman Illustration
https://www.youtube.com/watch?v=NmM9HA2MQGI
Fundamentals
npub12eml5kmtrjmdt0h8shgg32gye5yqsf2jha6a70jrqt82q9d960sspky99g
AverageGary
npub160t5zfxalddaccdc7xx30sentwa5lrr3rq4rtm38x99ynf8t0vwsvzyjc9
In this episode, we dive deep into the fascinating world of elliptic curves and their significance in cryptography. We start by discussing the basics of elliptic curves, particularly focusing on the polynomial equation y² = x³ + 7, which is crucial for Bitcoiners. We explore how operations on these curves, like adding points, form a group and why this concept is important.
We then delve into the textbook by Neil Koblitz, which highlights the importance of elliptic curves in cryptography. The discussion transitions into the axioms of groups, such as closure, associativity, identity, and inverses, and how these relate to elliptic curves.
Our conversation takes a turn towards Fermat's Little Theorem and its application in cryptography, particularly in computing inverses in finite fields. We explore how this theorem simplifies calculations with large numbers and its implications for public key cryptography.
We also touch on the Diffie-Hellman key exchange, explaining how it enables secure communication over the internet by deriving a shared secret without exposing private keys.
Throughout the episode, we emphasize the importance of understanding these mathematical concepts to grasp the underpinnings of cryptographic systems, especially in the context of Bitcoin and other cryptocurrencies.
[00:00:04]
Unknown:
Yeah. It'd be a shame if we did this entire show without recording it. Absolutely. That's what we're about. Were just about to say. We're ten minutes in to to doing that. Hello, everybody.
[00:00:17] Unknown:
Average Gary here.
[00:00:19] Unknown:
Fundamentals. Good to see you guys. We were just,
[00:00:24] Unknown:
we were just talking some math off camera. You're teasing me with something. And I said, woah. Pause. Let's hit record here because Yeah. I think what you're about to say is important to the overall objective here.
[00:00:36] Unknown:
Yeah. So, I posted out of the Nostra account this morning something that I found in a textbook this morning looking at, elliptic curves. Yeah. I think we all know what an elliptic an elliptic curve is. We kinda know. We know they're important. Well, let's We know the picture. We'll we'll post that. I'll post a picture to the Nostra account. We've posted a picture of an elliptic curve in the show notes before, but we'll have it in the Nostra account so you don't have to fish around for what episode it was. And to be clear, the curve though is defined by an equation,
[00:01:14] Unknown:
a polynomial equation. Yes.
[00:01:16] Unknown:
Yes. And the one by a polynomial equation with certain restrictions.
[00:01:21] Unknown:
The one that we care about is called sec p two fifty six k one. Yes. And it is y squared equals x to the third plus seven.
[00:01:33] Unknown:
Yes. That's the one we care about.
[00:01:36] Unknown:
At least as Bitcoiners. Sorry. Continue. Bitcoiners. Yes.
[00:01:40] Unknown:
And you guys kinda know what it looks like, but everything we do is on it relies on either adding points on the curve or, adding a point to itself, which is doubling the point. Right? So, like, everything is really essentially based on adding two points on the curve. And, I was I'm going through I am going through personally a textbook by Neil Cobblets, who I think invent it is not that he invented. I hate to invent was it invented or discovered in conversation? He put the words words what he discovered. But that he kind of discovered, the significance of elliptic curves for cryptography.
And they might have called them cobblets curves at some point in time. But so I'm finally on the chapter on elliptic curves of his book. Been going through it since we started the show. And, you know, you think about the conversations we've had so far, and they've been difficult. Right? Like, I think the one where we talked about groups was great, but it was hard for people. Like Yeah. I mean, my daughter is a math major, and she's not gonna see what a group is still for a couple of years. Like, they don't you just don't jump right into that stuff. But, one of the things I remember discussing was we don't know why it matters to call something a group, but we know that it does. We know that that, like, confers information on our on the thing we care about.
[00:03:19] Unknown:
And that information is the interaction between the elements of that group. Well, that's
[00:03:27] Unknown:
yeah. Yes. So, like, in the so I'm I'm reading the Cobblets book. I get to his chapter on elliptic curves. And in the first paragraph, he says the points on an elliptic curve. Right? So imagine you draw it out, in your x y, you know, your x y graph. Your points x and y that are on that lie on the elliptic curve, if you take all of them together, they form a group. This is what I read. And I'm like, woah, this matters. Right? This relates. So here here we are now. Something is now called a group, and it's important that I know it's called a group, and the question is why. Right?
And so, if I go back to then the axioms of the group, right? The first one, and by the way, it's under an operation. And in the operation of elliptic curves, we know is addition is the one that we use. So we're gonna say, okay. So it's a group under the operation of addition. And the first axiom was that was called closure, which meant that any two elements in the group that add that are added together results in something that's also in the group. So in the case of the elliptic curve, any point, any two points on the curve that you add to each other is also a point on the curve.
[00:04:54] Unknown:
Right.
[00:04:55] Unknown:
That is powerful. So we're gonna kinda, like, take a step back for a second and internalize that. Well, it means that we can do these operations
[00:05:04] Unknown:
without going outside the bounds. Right? So like these group, like the, the closure of it is because there's like, if you can think of it as a physical structure, right? Like a group of things, you can't, you, you can't go outside of this. It's, it's closed. It's completely closed. You can't go outside of it using this operation, this operation specifically being addition. So anytime you add a point on the sec on an elliptic curve to another point on the same curve, you will fall within the curve still.
[00:05:37] Unknown:
Yeah. Which that that is like, if you look at maybe other types of, other types of linear like lines that you might or curves that you might be familiar with. Right? Mhmm. That's not a common feature. Right? So if I took the the line y equals x, which is like a diagonal line through the origin. Mhmm. Y equals x. So you have the point zero zero. You have the point one one two two three three. Yeah. Negative one negative one. Right? You take that line. Right? Well, the only way, well, that that you would have. I think you'd have closure on that line. I think any two points added together on that line are on that line. So I think that is like a rare probably a rare example.
Maybe maybe it's not. Maybe it's a com maybe that's actually pretty common. I have to do the math. I'm more you know, I have to do the math on that. But maybe any two points on the line are on that line, and that is kind of interesting too. Right? But so we have the so and that's maybe why it you know, I don't wanna get too far down that rabbit hole, but the t and the elliptic curve for people who have you know, part of when we do this when we started doing this show, we were thinking about people who maybe have some experience in cryptography but don't understand the math. And I think anyone who has experience in cryptography knows that we add points on the curve, and it's very important to know that the result is also on the curve. We're dealing with points on the curve. Right?
So, like,
[00:07:14] Unknown:
that is That's even that's how you can check, like, no. Hold on. Where was I going with that? Like, you can check that a point is on the curve. Never mind. I'm sorry. I was I was you you just evaluate the equation to check that the point's on the curve. Like, you can you can val I guess what I was getting at is, like, you can validate this. If you do x plus y equals whatever this is, you can go plug that result into this equation of the curve itself and validate that you are, in fact, back on it or still on it, rather.
[00:07:50] Unknown:
Yeah. That's right. Now adding points on the curve visually is not like, it doesn't look like doesn't look the same as you would do on a on, like, a u on a Euclidean line. Right? You I'm sure there's a a video we can find to that goes through all that goes through all that. But I thought it was really I don't know. It really was amazing to me to see those words to, you know, to see Cobblets find it important to say, oh, the points form a group. So, again, this is gonna matter. Like, the knowledge that the points on the elliptic curve are a group is going to matter. We don't exactly know why. Right?
Yeah. We just know that it matters to be able to call something a group. So I just I wanted to go back to that. So sorry to anyone who, like, thought that episode was particularly painful. But, like Well this stuff is gonna like, this is how the story gets weaved together.
[00:08:50] Unknown:
And to try to reiterate what these axioms were. Right? The the first was closure, which, you know, a and b, If you do those operations together, you get c, which is also in the group still. Yep. The second is associative, meaning you can multiply a or you can do the operation. Right? In this case, addition. You can do the operation in any sort of, like, grouping order. So whether you do a and b first or b and c first,
[00:09:17] Unknown:
it doesn't matter when you then go do the three elements. B and c. So in other words, you have three, let's say, three elements. Right. Whichever two you choose first doesn't matter.
[00:09:28] Unknown:
You're still within the group.
[00:09:30] Unknown:
Yep. And then the the last is the the neutral element. So there's an element of of one. I like the identity is the name for that element. Identity element. Yeah. Actually, sorry. So so in in under addition, it's zero. Under multiplication, it's one.
[00:09:48] Unknown:
And is that the
[00:09:51] Unknown:
I'm trying to remember back. Is that the infinity point or the So in the elliptic curve, that's right. That's right. And that and and the under the elliptic curve, I like, I know from, say, Jimmy Song's programming Bitcoin textbook that there's an there's something you call an infinity point. I never really it seemed like either a zero or something like that, but it was never really clear what it was there to sort of make it all work, but it wasn't really clear why it was needed. Now it's like, okay. So now we also know there's an identity element of that group, and we they call it the infinity point.
[00:10:28] Unknown:
Right.
[00:10:29] Unknown:
But in a general group of addition, it's zero.
[00:10:33] Unknown:
And the property of this is that in that identity element times any other element gets or I'm sorry. Yes. Plus plus plus. The identity element Yeah. Plus
[00:10:47] Unknown:
any other element in the group gives you the same element back. Yeah. In other words, a plus the identity element equals a. Anything plus the identity and and the identity element equals itself.
[00:10:58] Unknown:
Right. And there is a an inverse of a. That's right. Right. So if a is an element in this group, there's an inverse and you can take a plus its inverse, and you get the identity element.
[00:11:13] Unknown:
That's right. And so in addition, it's negative. It's the it's the negative or with the opposite. Right?
[00:11:22] Unknown:
Yeah. That's always the inverse and then of addition is negative. When you'll see the inverse represented as a to the negative one power?
[00:11:32] Unknown:
Sometimes. Yes. Which, again, you see a lot of notation that is assumes multiplication. That's how you would think about multiplication. Right? But when you're dealing with groups generally, you might see that notation even though it's even though the operation isn't necessarily multiplication. But you still might see it, you know, you might see it written that way. Right? Yeah. So the inverse of an element in a group that's using the operation of addition is just always the negative of that number.
[00:12:05] Unknown:
One and I came across the, one of the reasons why like, one of these theorems. So in the understanding cryptography PDF, there's Fermat's little theorem. Right? Yeah. Which is basically element a
[00:12:21] Unknown:
raised to Sorry. Sorry. Sorry. Before you move on, I I can feel it. Yeah. I can feel we're moving on to another track real quick. I just wanted to go back and say, by the way, it wasn't just a group that the points represent. They represent they're actually an an abelian group, which means that it has the additional property of commutativeness which means that the order, like, the the order of, the left and rightness of the of multiplying them. Sorry. Right. The left and rightness of adding them doesn't matter. Meaning a plus b equals b plus a, which sounds obvious. Why did I just spend a minute even discussing that? But abelian groups have special properties too and I think we will find out why it matters with elliptic curves.
So I wanted to just get that out for completeness because I know we're about to move into something else.
[00:13:14] Unknown:
One and again, just to, like, really complete so closure, associativity, identity, inverse
[00:13:22] Unknown:
Yep. And communicative are like the five. Is not an axiom, though. No. It is a feeling group. It's a potential additional property of a group. But you don't a group it's kind of like, you know, like a quadrilateral is a can be a rectangle, but a rectangle isn't always a quadrilateral. Or a square is always a rectangle, but a rectangle isn't always a square. Right. Okay. Right? So a group can be abelian. Abelian group is always always meets the four axioms, but meeting those four axioms doesn't mean you're
[00:13:59] Unknown:
Abelian. Abelian.
[00:14:00] Unknown:
But under addition, typically, addition is typically always in a sort of a feature, always has that property typically. Subtraction doesn't. So, like, anyone can now take a pen and paper, and they can see for themselves that subtraction is not if that's the operation, if that's not a b like, it matters. It does. Yeah. Yeah. Five. What's first. Right? Yeah. Five minus two is not two minus five. Right. Right. Right. Right. You can see that. So it's not always the case, but we know for elliptic curves, it is the case.
[00:14:35] Unknown:
Under addition? That's right. The the identity piece of groups or, not the identity. The inverse piece of groups Yes. For Matt's little theorem.
[00:14:49] Unknown:
Yeah. Okay. Yeah. Now I see where you go. A is an integer
[00:14:53] Unknown:
and p is a prime number, then a raised to the power of p is congruent, which we covered this before. It's like it's like not equal, but it's like the same ish.
[00:15:06] Unknown:
Yeah. When I'm using mod. Let's let's just load up an actual example. Maybe p is five. Okay. Right. And you so because we've done this in the past. And let's just quickly Yeah. Yeah. Go through the number two. Right? Two raised to the one is two. So two can generate the entire group. Right? Yeah. Two two raised to the one is two. Two raised to the two is four. Four. Right? Two raised to the third power is eight, but mod five is three. Yep. So two to two is now so we've generated two, four, and three.
[00:15:42] Unknown:
Right? Yep.
[00:15:43] Unknown:
And, next is 16. Right? Two to the fourth power is 16, which is actually one. So now it took you to the fourth power. Two to the fourth power turned out to be the identity. Two to the fourth power gave you the identity, which is one. Right? The multi and this is all under multiplication now. Right? This this is now all under multiplication. So two to the fourth power in mod five is one. K. Four is five minus one. Okay. And any multiple of four, I bet you, any multiple of four, if you raise two to that power, will give you one in the mod five. You wanna try it with two to the eighth?
Let's try it with two to the eighth. Two forty eight. Two Two thirty two sixty four. Two fifty six. One twenty two fifty six. Yes. So two fifty six is clearly one mod five. Right? I don't know. I have to do that, guys. And I guarantee and so the power of this is that you know that two to the eightieth is gonna be one mod five, which means if I said if I asked you what's two to the eighty first power, then it's two to the eightieth times two. Two to the eightieth is one. So I can tell you quickly two to the eighty first power mod five. The answer is two. Alright. Let's let's go over that one again. Oh, okay. This might be my first video that I that I that I do for this group. Okay? Yeah. Yeah. Yeah. Yeah. I'm gonna do two to the eighty first power by hand and prove to you that the answer is two.
Okay? Because this is the power of Fermat's little theorem is that you can you have this knowledge that two to a power that's a multiple of one less your prime. Right? You back one off your prime. So your prime is five. You back one off and you now have four. So two to the fourth power is one and you go through this cycle. Right? You go through five, six, seven, eight, and you get one again. You do nine, ten, 11, 12. I'll do this in a video. You get one again. Oh, okay. Yeah. Yeah. Yeah. It's just so every four times you multiply two by itself, this element, it's because that's the two's called the generator. Anytime you have this generator and you, in in a prime field, that's it's it works beautifully.
So I could tell you that I mean, you pick any number. Literally. Literally. Get pick any tell me a three digit number right now. 173. Okay. Two to the +1 power. Okay. Yeah. I I can tell you right now is the same as let's see. It's so it's every four. What's 173 divided by four? I should have brought my calculator with me to this podcast. So let me do it real quick. Okay. So one seventy two to the one seventy two equals one. So that's gonna lead I know the answer is two. So write that just write that down and text it to me so I can demonstrate that in a video. Alright. I'll text it. The one hundred seventy third power. I know it's gonna be and and and a mod five.
So I hope like, what I think is happening right now is what Fermat's little theorem did for me is showed me how, it's possible to really multiply the power of modulo and the power of remainders enables us to start to do arithmetic with really, really, really, really big numbers. And numbers so big, this is part of what we were talking about before we started rolling. Like, at some point, you're going to be doing arithmetic with such big numbers that there's no way in your lifetime you can even check yourself. So this is why it's, like, important to understand on the ground you stand on, at least, how to do this with what you can see and prove now. Like, in other words, two to one two to the hundred and seventy third power is nothing compared to what goes on in public key cryptography.
You know? Like, it's nothing. It's really tiny tiny number.
[00:19:56] Unknown:
What brought me to this Fermat's theorem is we were talking about the properties, and it and it says that one of the uses, one application of this theorem is computation
[00:20:06] Unknown:
of the inverse in a finite field. Yes. And this is in programming Bitcoin, by the way. That the first time I ever heard of Fermat that there was something called Fermat's little theorem was reading the book programming Bitcoin. And I probably talk about this book every episode here because Right. It's the thing that kinda woke me up to the fact that there's this I didn't even know there was this man. Right? But that I mean, I I don't know about you guys. That kinda blows me away that I can I you know, one of the greatest things you can do in math is eliminate a giant portion of what you're trying to of what you're trying to calculate? Yeah. Copy computational shortcuts. Two to the one seventy three, and you know that two to the one seventy two is one. And you just put a big slash through that, and you're left with that times two.
Right? That is incredibly powerful. And also from a cryptography perspective, I think it should put fear in us to say we have to be really careful about if it's that easy to reduce certain numbers. Right? We gotta be careful and make sure we're not that we're not dealing with Fermat numbers in with our secrets. Right?
[00:21:24] Unknown:
Yeah. Because you don't want them to be reducible.
[00:21:28] Unknown:
Correct. Like the whole point is to say, well, the whole point of what we're doing in cryptography is to take all of those tools out of the hands of people who would try to guess our secrets. Right? And then say that's the only way there. The only way you're getting Just by guessing. You're getting into my door is by being a a lucky idiot. Right? There's not you can't there's not like like, there's nothing you can do on this world Yeah. To, eliminate a single arithmetic operation, my friend. And that's so, you you know, Fermat's little theorem is really powerful. Really, really powerful, and I can't stress it enough. I think that I like, it's I am going I'm determined to do a good video for you guys. On for Matt's little theorem? On this. Yeah. And that's like and and it was saying in here too that it was for Matt's little theorem is is
[00:22:24] Unknown:
just almost like a special case of Euler's theorem.
[00:22:27] Unknown:
Yeah. And that's what I knew. When you started texting me last week that you were gonna you're looking at Euler's number, I was like, okay. For Matt's little theorem, it's got to be
[00:22:36] Unknown:
Oh, is that how you say it? Oil e u l e r spoiler.
[00:22:40] Unknown:
I don't know. I mean, it's still funny, dude. This is the second time you got the same phonetic. I I used to say that too. I used to say you Yeah. To me, it's Euler. Euler. You You know? Oh, this is not an English podcast. It's Ferris Euler's Day Off. Yeah. Exactly. For me, that's how I heard it. You know? And I think I was corrected again. This is the second three. I think we did it I think we got there with Galois too. It's like I was walking around going to Golois and all this stuff and
[00:23:06] Unknown:
Galois. Okay. So it's not Golois. It's not Euler. It's Galois and Euler.
[00:23:12] Unknown:
I think that's how I heard the highly regarded people who inform our knowledge system say these things. Alright. Alright. That's what I all I could say. So for Matt's little theorem is really powerful, and I I guess what I wanna clarify here is it's it's specifically when your modulo is prime. Right. And because when I don't I think it's too much of a leap to get to Euler, to be honest. And I mean, I'd almost rather not do it. Just I I I think it it or maybe we get to it by the end of this episode, but I think it's important to understand that, if if you have a prime number like five, right, what you wanna what what is the field generated, right, by that, like, by that modulus. Mhmm.
Anytime the modulus is prime, there's a a group it's called an Euler group. But, it's all of what is the group that has basically all of the numbers quote unquote this okay. I haven't we haven't talked about co prime. We haven't talked about greatest common divisors. We haven't we haven't talked about real I think we touched on greatest common divisors. Relatively prime? Did we discuss relatively prime? No. We didn't, but I had a highlight in here,
[00:24:40] Unknown:
for Matt's little theorem. And it it it said, the theorem is helpful for primality testing and in many other aspects of public key cryptography. But for whatever reason, when I read that word primality, my mind went to, like, primal as in, like, the idea of, like, things that are, like, fundamentally,
[00:24:58] Unknown:
like, buried deep within. Right? Like, when you think, like, primal instincts Double meaning. Some of these really do. Like, I always when I first heard of a discrete logarithm, I thought it was discrete like secret. Yeah. Like a natural logarithm. Not to but and I think it has I love it. I love it. It has, like, a double meaning because discrete really is that it's non continuous. Yeah. So I I, anyway, so let's talk quickly about what it means for two numbers to be, relatively prime. We know what it means for one number to be prime. Correct? We know that it the number that who that has no factors other than, like, itself and the number one. Yeah. Right?
So if I said There are no
[00:25:42] Unknown:
let me let me try to, like, say this a different way. Any other yeah. Yeah. There's there's no numbers less than itself that can be combined together to give you this number. Right. So, like, seven is an example, and this is, strictly speaking, multiplication.
[00:26:02] Unknown:
Right? Like, so It should say no real numbers. That's no. Nothing Yes. Nothing, because you can actually find complex numbers that do this. So it's what? Three, five, seven, thirteen, like, are, like, the Two two two is also 2. 2. Yes. So 2357.
[00:26:19] Unknown:
2 3 5 7. 11 13 7. 11. 19. And that's just because there's no numbers that you can multiply to get to. Yeah. No real numbers that you can multiply to get to that number.
[00:26:30] Unknown:
Now this is easy to do, pretty easy to do if they're if under 50. Under a hundred, you need a little bit of time stable experience probably. But when you start to get to numbers that are five digits long, like, if I said 10,001, does anybody know if that number is prime or not? You're gonna just get in your calculator and start trying shit. Right?
[00:26:54] Unknown:
Until you Was any number ending in one prime though?
[00:26:57] Unknown:
Sure. Any number ending in one? 30 one. 40 one. Right. Yeah. Those are prime. Right? Yeah. I mean, plenty of numbers ending in one could be prime. Right? Yeah. Yeah. Yeah. My point is, yeah. So, like, for 10 a number like 10,001, the like, primality testing is, like, a lot of what we talked about how much arithmetic I do. A lot of it is just doing some of these primality testing algorithms by hand. Mhmm. Because and they're they're interesting. Because basic they're more, they're more powerful and more effective than just the brute force of plugging numbers in and seeing if you get another integer. Right? Because that's what you'll do with 10,001. You'll plug 3. Maybe you know it's not 3, but you'll plug in 7, and then you'll plug in 11. And you'll go up to the square root of 10,000. You'll go up to basically a hundred.
[00:27:55] Unknown:
Right? Yeah.
[00:27:56] Unknown:
That's all you have to do. And then you'll figure out if that so but, you know, that could take a really long time. What if I said a million and one? What if I said a billion and one? I mean, it's gonna it's you know, it starts to take a really long time to To go through the To do all that. That's so it's just a so let's go back to, primes. Right. K. Just regular prong, stuff we know. Number five, seven, you know, 11. Now there's this concept of two numbers being relatively prime. And what that means is that so technically it means their greatest common divisor is one.
But intuitively intuitively, it just means that there's no they don't share a common factor. So if I took the number six and twelve, obviously, you can see that they share a factor and they're not, Those are not relatively prime to each other. Right? Nine and twelve are not relatively prime to each other. You can see that they had shared the three. Three. Yeah. Right? But, like, nine and seventeen are relatively prime to each other. I think probably I'm trying to think of two numbers that aren't prime. Right? Like, ten and twenty one.
Right? 10 is five times two. 20 one is seven times three. They share no common factor. So those are relatively prime.
[00:29:29] Unknown:
Okay.
[00:29:31] Unknown:
Okay.
[00:29:32] Unknown:
Why does that matter?
[00:29:33] Unknown:
Yeah. Good question. So that's the always the next question. Why does that matter? Okay. So let's sit on that. Let's sit on that. Always have that question in our mind. Right? But Mhmm. But we're not gonna stop because we don't have a great answer. We just, like it's almost the flip side of that question is, like, it's not like why does this matter? It's more like, oh, in a curious way. Can you do with this? Wonder why this matters. Okay. Yeah. Yeah. So let's just keep that until until the light bulb goes off. Right? So now when you go and we talked about creating a group that's modulus a number, like five. And that number was that group consisted or that finite field consisted of numbers the numbers one, two, three, and four.
Right. Right?
[00:30:22] Unknown:
Yep.
[00:30:24] Unknown:
Because, they are you can generate a field, that is, the members are relatively prime to the modulus, to the thing you're dividing out. And when in that number is prime, it's always going to be all of the numbers prior to that number. So So I'd say that you can you can create In other words, because one, two, three, and four are all relatively prime to five. And that's the same is gonna be true of seven. The same is gonna be true of 11. Right? Let the the field of numbers relatively prime to 11 is always gonna be the digits. All the numbers. Zero to you know, all the numbers through 10.
[00:31:11] Unknown:
Oh, because a prime number itself, like anything less than a prime number, is just relatively prime to it by default because it's a prime. That's why it is a prime number. So that's what makes primes
[00:31:21] Unknown:
special that you could generate a field. And this is literally page one of the book Programming Bitcoin. It went way over my head. I didn't understand. Okay. I'll just go revisit that one again. This is on page one of that book. Not to shell that book too much, but I've that's Yeah. Worth that book is worth promoting because of because of how good Because of the entry point. Yes. And it it brings to bear all of these things, and you don't have to know any math to, like, go through the book. But, like You don't because I skipped over all that stuff and went right to just programming it. But it all wakes up when you start to see okay. Yes. You can generate a finite field modulo a prime, and that's gonna give you all of the digits less than that prime.
[00:32:07] Unknown:
You're right. Right?
[00:32:09] Unknown:
Okay. And so now what happens the question is what happens when your modulus is not prime? Okay. So let's say we wanna generate a group modulo nine.
[00:32:25] Unknown:
Yeah.
[00:32:25] Unknown:
Now, let so let me take and and and the group's going to be all the numbers relatively prime to nine. And I'm going to just do this in my head that it's going to be the number one, number two, not three. Right. Yet. Right. Yes to four. Yes to five.
[00:32:48] Unknown:
No to six. Not six.
[00:32:50] Unknown:
Right? Yes to seven, yes to eight. I should have picked a better one. But, let's do 10. Okay. Okay. Let's do an even let's do 10. So yes to 1. It's 10. We have +1, 379. When's your first numbers? Again. So noted obviously, all the even numbers are no's. Right? And 5 is a no. Right. So we have +1, 379. Okay. Okay. And guess what? So you talked about you talked about the Euler number. The Euler number is the number of elements relatively prime to that number. So in other words, the Euler number of 10 is is the number of elements before 10 relatively prime to 10, which is four.
Now, keep the number four in your keep the number four alive right now real quick because Yeah. What we're gonna do is pick an element of that group. Call it three. K. Okay. Okay. Three to the first power is three. Yep. Alright. Three squared is nine. Remember our group, one three seven nine. So we've now three squared. We're gonna generate this group. Okay. And we're gonna figure out when we get back to one. K? We're gonna Okay. Take try so three squares modding by 10? Modding by 10. Okay. I feel very lucky because I picked a great number to mod by. It's very easy to mod by. Three third is 27. 20 seven. So that's seven. Right? So we've generated Yeah. So we've generated three, nine, and seven so far. Right?
Which which element are we missing? We're missing one. So let's hope three to the fourth, which is 81, there's our one. So now, like the so it's like this analog to Fermat's little theorem. Fermat's little theorem, it was always prime less one. Yeah. But it just so happens that that is the number of relatively prime elements to that prime. So Euler generalized it. You know, Fermat was not even a mathematician. Fermat was a lawyer who just spent every waking hour doing these calculations in his head, and he was a fucking genius. Right? But Euler So basically Yeah. Euler generalize this.
[00:35:17] Unknown:
The elements in a group mod whatever. Right? Mod a number. Is my subgroup? Of co prime numbers in that group.
[00:35:31] Unknown:
Yeah.
[00:35:32] Unknown:
If you take any element in the group and and raise it to the power of the number of co primes there are. That's the power that makes you makes it one. Yes. Then you get one.
[00:35:42] Unknown:
It assuming you that's a generator. Yes. That's assuming, like, that number is a generator. Right. And and when we say one, it's like We got lucky that three is a general I mean, I we could test it out with the other elements in the group. I don't know if they're all I don't know if they all are. I think they are. What's 7? So we can do 7. So 7 to 1. Just 7. 7. 7 here it is. 49 is nine. 40 nine is nine. Three. Yep. And then what is seven to the fourth? I think the mod is 9 on that. I'm not Seven to the fourth is 2401. Oh, boom. Mod 10 is one. Yeah. So there you go. So seven also generates all four elements of the group.
So now this is even more powerful than Fermat's Little Theorem. If I said, what is, in mod 10, what is seven to the, you know, eight thousand nine hundred and sixty eighth power? Right? I just have to figure out where the four, how far the so eight, nine, six, eight. That's actually evenly divides four. That's one. So I know that nine to the eight thousand nine hundred and sixty eighth power, modulo 10, the answer is one. Magic.
[00:36:51] Unknown:
Any multiple
[00:36:52] Unknown:
divides four. Yeah. That's right. So add add to the power of any multiple of four because modulo 10, there are four co prime elements. Right? So it worked for Fermat's. Fermat's little theorem is so cool because you don't have to think about co prime. It it is true that the prime minus one is the number of co prime elements. And you don't have to Because otherwise, you're gonna have to calculate all these co primes to get that number. So for modulus of the number, it allows to, like, boil this down only for prime modulus. Yes. It it's really easy to understand for primes. Euler basically allows you to do this for any number.
Right? You can say, well, it's raised to the Euler number, which for a prime is prime is that prime minus one. Pretty fucking cool. These are the videos I'm going to make, and it's okay if they suck, people. These videos suck, but it's gonna be cool to walk you through this. I really really want to do this. You'll find those on on Oster only.
[00:37:55] Unknown:
The end file will be in the show notes. Well, maybe somewhere else, but
[00:37:59] Unknown:
I'm definitely not sure. YouTube channel for this.
[00:38:02] Unknown:
Yeah. That's all. YouTube, Rumble, all of them. Put them everywhere.
[00:38:09] Unknown:
So that was an inch I mean, Jesus Christ. I I hope that wasn't too obtuse for people. Right? Well, let's see if we can try it. Fundamental things. These are really fundamental concepts of at least cryptography. And like I said, we're talking pay like, we're talking chapter one of programming Bitcoin. Mhmm. You'll find you will find all of these things. So, you know, if you can find yourself that book somehow, I would definitely check out, like, yeah, check out the first chapter. Available online as a PDF. K. Good. Yeah. And I think it's on the GitHub too. Like, I think you can go on on their GitHub, which I'll link to the show notes again. Fermat's little theorem, Euler's number, and this is really how this is part of how you calculate so when you're doing elliptic curve, this goes back to when you're trying to add two points on an elliptic curve. Maybe I'm heading for white water here. Maybe I really screwed up. But I think that I do think that somehow this is used in calculating the inverse, on the elliptic curve. It is. Yeah. Modulo that prime. Yeah. But then why is an inverse important?
[00:39:27] Unknown:
Right? Like, why is being able to calculate that inverse important?
[00:39:32] Unknown:
Yeah. We'll get there. Okay. We'll get there. Right? But it it it seems intuitive just like two dudes talking about Fermat's Little Theorem. It seems intuitive that being able to calculate an inverse, particularly the the one that equals one, especially if that scales to all out to, like, all of the exponents that are,
[00:39:57] Unknown:
you know, that have a certain Yeah. It doesn't matter if it's a certain multiplicity
[00:40:01] Unknown:
that it's very powerful to be able to eliminate, you know, just eliminate a portion of your calculation.
[00:40:08] Unknown:
And correct me if I'm wrong, and maybe this is me gonna try to divide. I'm sorry. So, like, in inverse is called is also division.
[00:40:14] Unknown:
The same way subtraction Well, subtraction. Yeah. You Division. Add the inverse. You're subtracting. Yeah.
[00:40:19] Unknown:
So if when you when you wanna when you wanna subtract something and you only have addition available Mhmm. You can just add whatever the inverse is. And isn't that what the elliptic curve point addition uses? Is it like you end up adding and then taking the inverse of whatever that answer is?
[00:40:39] Unknown:
Yeah. I I we'll hold on. Go there. We'll not go there. I'm not confident enough. I feel like I've already stepped in a bear trap because I'm not clear on how we get from addition in elliptic curves to what we're talking about, which is happening in the multiplication space.
[00:40:56] Unknown:
Well, multiplication is That's not clear. Just adding over and over again. Right? Like, three times six No. No. Yeah. Six plus six plus six.
[00:41:05] Unknown:
This this idea of of no. Yeah. I understand. But now we're Mhmm. We're we're we're in multiplication, you're using powers to essentially do the same thing, and so it's a different operation. And I think it's probably because it I don't wanna get I don't wanna get too much into it, but it goes back to a you know, it's also it it's also a ring. A field is a ring that contains both addition and multiplication and allows for both operations. And I'm guessing that is I'm guessing we're killing people right now too. But, like Well, that's fine. We'll get there.
[00:41:40] Unknown:
I was looking you know, the next sort of, like, part of this this PDF that I was gonna look into is, like, okay. It goes into RSA, but I don't I don't, like, I'm gonna skip that. And that's a great motivator. RSA is a great motivator
[00:41:53] Unknown:
for the stack that I continue to, like, say is, prime numbers, Euclidean algorithm, division algorithm, algorithm, Chinese remainder theorem, Euler's number, Diophantine equations. This is a stack that we I wanna, like, get to all that's a number theory stack that gets you essentially to public key cryptography to to discrete logarithms.
[00:42:17] Unknown:
Right. And that's the next sort well, that's not the next piece in the book. If I skip over the RSA chapter, it's Diffie Hellman key exchange.
[00:42:27] Unknown:
Yeah. And I I'm happy to continue to just read this table of contents every episode because it's it's like how you guys will see it in a book and say, okay, I've seen enough people mention these things together that this is probably, you know, an important thing to learn.
[00:42:44] Unknown:
Well, it calls out so in the introduction to public key cryptography, it calls out essential number theory for public key cryptography, Euclidean algorithm, extended Euclidean algorithm, Euler's five function, Fermat's Little Theorem, and or Euler's theorem, which we've gone over all of those at this point.
[00:43:03] Unknown:
We've touched on them. We've touched. So and I think it's worthwhile I'm looking at time. I think this is good. We can I think we can articulate a little bit about public key cryptography and what goes on and how that just expanding on what we've done in the last forty minutes? For those of you who have stuck with us, God bless you guys. Public key cryptography. And I mean, you guys know this, right? And like, Gary, you know this because we just, you tell me, you were telling me this, right? But like the Diffie Hellman key exchange is based on two basically, two prime numbers that multiply out to a big number. Right?
Called a big number and and in the public space, everybody can know that number. Right? Yeah. Now, you know your component.
[00:43:57] Unknown:
Well, that that
[00:43:58] Unknown:
number is is probably referred to Hold on. So n is the is the is the combination of a times b. Both big numbers. You know a and I know b. Yeah.
[00:44:10] Unknown:
Right? Yep.
[00:44:13] Unknown:
And they're I don't know, like, I in fact, so, yeah, we know we we all know we all know our piece, and I don't wanna fuck this up too much. Why don't you go you know, I don't wanna fuck this up too much, but, like, it's basically based on you knowing the full number cannot back you into either the two numbers. Right? And that that's the nature of a discrete logarithm. You can't it's too hard to back into the two numbers that multiply out to that big number, and it can only be done by root force.
[00:44:47] Unknown:
Yeah. There's it it it's essentially there's a publicly known large number that both parties are then combining separately. And when you exchange those numbers, you're able to derive a common secret. Yeah. That's right. Or a common you're you're able to arrive at the same answer that can then be used as a common secret. Right? So one of the things is, at least in like software applications, you use Diffie Hellman when you're exchanging keys over the Internet to then have a shared key. Right? So a lot of symmetric ciphers, meaning the same key encrypts and decrypts, like that's a very efficient thing for computation.
And so it's used a lot for encryption on the Internet. Right? When you get your little lock icon, your SSL lock icon, that's that's because you and the server have done a Diffie Hellman key exchange, and now you have this thing called it's, you know, it's like a session ID or a session token, but it's essentially a shared, and that session ID or token might not be the exact thing, but it's there's a shared piece of data. There's a shared secret now that both parties are privy to that enable you to encrypt and decrypt in an efficient manner. But there's no exposing of that secret on either side. You're just exchanging public values. Right.
And then using the math too. So my secret and your secret, we combine it with this public value. And then by also again combining once I give you so you have x, I have y, and we have this public value of a. Right? I take a and raise it to x. You take a and raise it to y. Yep. And then we exchange those. Right? And now I don't know what your power was that you raised it to, But I can take the outcome of that and raise that to x
[00:46:40] Unknown:
and you or, to y This is look. So the way I always the only way I learned about this is from enlightening. And, like, when you so when you open up a lightning channel with somebody
[00:46:53] Unknown:
Yeah.
[00:46:54] Unknown:
And you're trying or even when you're trying to find a route to somebody. Right? Everybody is basically trying to, nobody really knows if the message is meant for them. But if you're, you know, if this process fails, then you know that this you're just a you're just a hop. Right? If this process succeeds, then you know that the payment is made for you. You know the message is made for you. Right? Yep. And that's without and that's how the two people know without ever sharing their secrets, but you they know the big number. Suggestions. I'm not sure what's yeah. Is that a video? You had a video going on there? It was a video. Yeah. And it was there's actually a great video on,
[00:47:38] Unknown:
Diffie Hellman key exchange from this guy
[00:47:40] Unknown:
that is Let's put this in the show notes for sure. Computer file.
[00:47:44] Unknown:
But it uses color mixing to sort of explain it. Right?
[00:47:48] Unknown:
Oh, yeah. I've seen this. This is great. Yes. I've seen it.
[00:47:51] Unknown:
Yeah. So if I have a color and you have a color and then there's like a shared color, if I combine my color with a shared color, you combine your color with a shared color, and then we exchange those two, we will arrive at the same color by, again, adding our color back into it on the piece that we exchanged. And so that is that's what this, like, this this video that he does. I found that he's been this Computerphile
[00:48:15] Unknown:
channel is great for sort of, like, explaining things. Yeah. Now if you exchange a number with somebody and that person is smart enough to know that it's prime. Right? Yeah. Yeah. They can back in to your secret. Right? So that's why it's so important that these numbers are so big that not even the primality testing algorithms that we know of are ever gonna be able to break them down. And, like, you're never gonna know that their number is they'll never know if their number is prime. Although, I don't I might have just stepped in shit again, but, like, you know, it it's that that that I'm this is the idea, though, of, like Well, it's because the why we use big it's why we use big numbers. And, you know, for Matt's little theorem, it does allow you to really buzz saw into a large number if you happen to know that it's raised to a you know, if you know the modulo, which we do in Bitcoin, it's gigantic.
[00:49:20] Unknown:
Right? Right. The generate pointer is known. Yeah. But that that generate report is co prime to all the other
[00:49:30] Unknown:
points. Has to be. You can't be. Yeah. Must be. And that's why the like, when we talked about that group modulo 10. Right? Yeah. It's the unit group is called, and these are all the numbers co prime to 10. Those are all basically, those are all the generators of that group too.
[00:49:47] Unknown:
Right.
[00:49:48] Unknown:
Right? Right. You have to be and there's a, like, there's a lot of very tedious theorems that prove all this that I don't think I really recommend. I think this is the good level to just understand that being co prime to the modulus makes you actually a generator now of that group. So one one five except well, you know, not one, but three, five, and sorry. Three, seven, and 10 were were generators. Three, seven, and 10 were generators of that group.
[00:50:25] Unknown:
Well and and I think if we if we if we go back to, I think, our first episode while we were talk you were giving us a story on why this is important to you because you got to these, like, giant numbers in the sec p two v six k one, and you were like, what is why what does this even mean? I saw a wall of numbers. Yes. I saw a wall of hardcoded numbers and not formulas and just panicked.
[00:50:48] Unknown:
Well, but I I think I think I know what they are.
[00:50:52] Unknown:
Understanding this one aspect of the generator point is co prime to all the other points on the elliptic curve is like a critical thing because it it does not allow because there there are no shared factors, it doesn't allow you to, like, back into the number.
[00:51:11] Unknown:
I don't know that they're co prime to all the other points. I think that but they're co prime to the modulus.
[00:51:20] Unknown:
In other words Oh, the generate yeah. You're right. The generator is not the modulus.
[00:51:24] Unknown:
Like, 35 sorry. 37 and 1379 are 39 are not co prime, but they're in this group because they're both co prime to 10. Right. People. Using yeah. Yeah. This is They're not co prime to each other. The points are not co prime to each other necessarily. Correct. They're co prime to the modulus, and therefore, they're generate that makes them generators of the group. But using a group
[00:51:49] Unknown:
mod a nonprime number. That's what I'm getting at. Using a group so when we use the the mod 10 example Yeah. Right? And we have those elements in there that are Yep. Like, not necessarily co prime to each other.
[00:52:03] Unknown:
They're co prime to 10.
[00:52:05] Unknown:
It is. Yes. But three and nine are not co prime to each other. What I'm saying is if we use 11, and that's a prime number, instead of using 10, now we have a guarantee that everything No.
[00:52:18] Unknown:
Because now you have all the numbers. Right? Two, four, six, and eight are all in that group, and they're not co prime to each other. They're never co prime to each other. You never have the, like, the groups the elements of that group are co prime to each other. You never have that.
[00:52:33] Unknown:
Right. And I think that's I think that's important though. Yeah.
[00:52:37] Unknown:
Okay. Yeah. Am I am I missing something there? I think we're all I I mean, we are I don't know. Okay. I don't know. This is a we're I think we're struggling we're struggling here probably the same way listeners are because we think it's like, you know, sometimes you think sometimes we think we're really on to something. And, like, for me, this is like I'm a musician and I can play, like, 85% of, like, a ton of songs and I start playing one and people start getting into it and then I hit a and then I forget. Like, oh my god. Wait. There's a whole point of the song. I don't know. And it's gonna be like, I'm gonna have to abruptly I'm gonna have to abruptly either try to pretend I know it or abruptly stop. You know what I mean? And I don't wanna get anything wrong here. Right? Yeah.
And so I think we kinda both started jamming on a song that we both knew 85% of and we hit a we hit a snag, you know. Well, this is the danger of us doing this. This is this is why I mean, this is a dangerous podcast for us. But But we're we're gonna we're gonna do it. We're gonna do this. We're gonna get we're you know, like, the discovery the upside of what we have to discover is so great that it's so worth it for me to do this here with you and to take this risk. Yeah. So I hope the listeners feel that way. I hope everyone who's gotten to this point, it's just like, yeah. Okay. I get it. Sometimes this fucking sucks. And I don't know, man. If you guys listen to this on, like, two x or three x, god bless you. I don't understand how to do it. Trying to get at was
[00:54:17] Unknown:
right. So so in elliptic curve cryptography, which is, like, the ultimate thing that we're trying to Yes. To truly understand here. There's a holy grail. We are using a prime modulus, right, to define
[00:54:31] Unknown:
I would think so. I would think so because then you otherwise, you have completely, sparse. Right? You know, the difference between using eleven and ten is the difference between having all 10 digits and having only four of them in your group. Right? Right. Right. Right. So it's it would make sense that the modulus would be always prime. So that you have a complete at least the complete group of integers less than that prime. Right?
[00:55:01] Unknown:
Now does yeah. I'm trying to think. So it because if if you if you're using, like, a mod 10 as your number, as your as your as your prime, order, Is it order when you're defining the field? Or I would just call it a modulus. A modulus 10. When you're using when you're using modulus 10, if you're not looking for this co prime to define your group, you're gonna run into issues of actually defining a group.
[00:55:34] Unknown:
Correct.
[00:55:36] Unknown:
Yeah.
[00:55:38] Unknown:
That's right.
[00:55:39] Unknown:
Okay. I'm just trying to, like, I'm trying to reason why why do you need a modulus of prime. Right? Why do you need a modulus of prime? I mean, it's I think it's let's just let's just stick with this discovery that
[00:55:50] Unknown:
it is a group. Like, those numbers form a group. The fact that one, three, seven, and nine actually form a group, and we can prove that too. We can say, look, three times seven is 21, and that's my one. Three times nine is 27. There's my seven. Like, all you can multiply every element in that group and get closure. Let's not take that for granted for for a second. Right? Yeah. Yeah. Yeah. That that it this is one of those things where we call the fact that you could even call a group is interesting.
[00:56:20] Unknown:
It is interesting. But again, getting back to, like, why prime to define the modulus for the group that you want? And I think having It's the same property, but you have all the numbers now. Now you have Right. Right. Right. Like a complete domain. You have a guarantee that everything underneath that number is is is part of the is an element in this group.
[00:56:39] Unknown:
And it would make it would make it much easier for an attacker to guess what's going on if he could eliminate three quarters of the domain.
[00:56:47] Unknown:
Exactly. Yes. That's what I was yes. Okay. Alright. So
[00:56:53] Unknown:
that's why I think the prime modulus, it seems to be I'm guessing, but, like, that seems to be why we would why that would be possible. A vast group. Right? Like Correct. The the the group is fast. Basically the most I don't wanna use terms that I should Huge. The most possible I think the largest possible domain, you know, when trying to guess, you know. Yeah. Could be wrong about that, but then again, it's just a guess. This is on this is where I am on the journey. All I can do is give you my best guesses right now.
[00:57:31] Unknown:
That's I mean, that's all anybody can do, right, is is explore, do the do the math,
[00:57:37] Unknown:
do more math. There are cryptographic schemes that randomize the modulus so that you don't know what a valid number is even to guess. Like, that would be kind of a that's possible too. I don't think that's the case for Bitcoin, but I do think that's potential that it would make sense to me for a general cryptographic scheme as well. Right? Where you ran you just flip around, like, your secret is the modulus potentially. And I don't but I I don't know how that would work. But it would make sense that you wouldn't even know how to guess. It would be very hard to attack that. Right? Because you'd be doing a lot of try a lot of thud tries because you're guessing numbers that aren't even in the group.
[00:58:20] Unknown:
Yeah. It allows you
[00:58:25] Unknown:
But in Bitcoin, we it's it's a where the modulus is a prime even though there there's no way to prove it. There's no way any of us can prove it.
[00:58:33] Unknown:
Prove what? That it's a prime? Yeah. Because to go through without using
[00:58:39] Unknown:
It's too big. These yeah. It's too it's too big to brute force because otherwise, you're just brute forcing everything. It's very hard to prove a number. It's very easy to prove a number is not a prime. You find a number that divides into it and eventually if like, basically, what what what it ends up is is it becomes a probabilistic exercise where you say, well, I am comfortable within point 001%. You know, I'm 99.999% confident because I've guessed such a large portion of the potential numbers it could be that no number I haven't found a number that divides into it yet. Right? But I don't have time on earth to test every number there is to see if it's a factor of this big 50 digit number. Right?
[00:59:27] Unknown:
So all you can do is say You can't do a holistic complete proof is what you're saying. You can't There's no way to exhaustively
[00:59:34] Unknown:
prove prove the only way to exhaustively prove something's a prime number is to actually divide every possible number into it. Right? Mhmm. And you forever. It takes half it takes half the number. So in other words, if I had if I was trying to figure out if, like, 10 was a prime, the square root of 10 is three point something. Right? Mhmm. So in other words, I can go to zero I can test one, two, and three because two, you know, you'll get all the higher you would multiply it by a number bigger than that. Right. Right. Right. Yep. Right. And then you get to three, and you're like, okay. It's three times three. If I did this with 10, it's like like sorry. I get to two, and I'd say, oh, it's two times five. Right.
[01:00:17] Unknown:
You don't need to go beyond the the midpoint. I don't need to test five again. Yeah. Yep.
[01:00:24] Unknown:
Right. So I can test all the numbers up to three. If I have a 50 digit number, I there's, you know, whatever the square root of that is is 75 digit number. And it's gonna take more time than you have on this earth to test that to test every single one of them. This is why cryptography works. Okay? This is this is also the reason why it's, you know
[01:00:47] Unknown:
Alright. Let's read Boost. Okay. I got them up. You got them up? Alright. Yep. I got them up. We've got, anonymous with a thousand sats. Great episode. Really like you in this format. So So somebody that's seen either you or me in another format thousand. Appreciate it. Likes us in this format. And, Glimmerin, thousand sats, it's good stuff. Simple, succinct, and I totally agree.
[01:01:16] Unknown:
And, thanks. Guys. I mean, I really appreciate communication, and I know there's some of you guys who have been like, please stop killing me here. And I know this is getting hard on some people, and, You know, bear with us. We're getting better. I love feedback. I as I said, I signed up. I've never had somebody boosts on a podcast. I signed Higher Truth I signed Higher Truth to feedback with boosts. Yeah. I say that semi jokingly, but only semi jokingly. Yeah. Yeah. Yeah. But I appreciate all the feedback,
[01:01:48] Unknown:
but and especially the boost. Well, it's it for me, I was like, I pulled up fountain and I was like, okay. Let me just go look at, you know, whatever. And I click over to, like, the the wallet tab, and then I was like, oh, wow. Like, people have valued this thing, and it was a motivation. Like, it was it was this is the first time that I've I've actually had, like,
[01:02:10] Unknown:
some people are streaming. So we don't see that here. But some people are streaming sets.
[01:02:17] Unknown:
Oh. Even still, like, just that that that just magic the magic Internet money magically lands in in my wallet.
[01:02:24] Unknown:
It's nice. It's just astounding. And so thank you truly to everyone. I mean, if if the video thing gets off the ground, that'd be nice too. I'm I'm really committed to especially the people who have stuck who've just stuck with us here. Like, I'm really committed to paying paying you guys off with, you know, knowledge and insights. And I just I have a strong belief it will. Thanks for sticking with us.
[01:02:53] Unknown:
We're gonna get there one formula at a time.
Yeah. It'd be a shame if we did this entire show without recording it. Absolutely. That's what we're about. Were just about to say. We're ten minutes in to to doing that. Hello, everybody.
[00:00:17] Unknown:
Average Gary here.
[00:00:19] Unknown:
Fundamentals. Good to see you guys. We were just,
[00:00:24] Unknown:
we were just talking some math off camera. You're teasing me with something. And I said, woah. Pause. Let's hit record here because Yeah. I think what you're about to say is important to the overall objective here.
[00:00:36] Unknown:
Yeah. So, I posted out of the Nostra account this morning something that I found in a textbook this morning looking at, elliptic curves. Yeah. I think we all know what an elliptic an elliptic curve is. We kinda know. We know they're important. Well, let's We know the picture. We'll we'll post that. I'll post a picture to the Nostra account. We've posted a picture of an elliptic curve in the show notes before, but we'll have it in the Nostra account so you don't have to fish around for what episode it was. And to be clear, the curve though is defined by an equation,
[00:01:14] Unknown:
a polynomial equation. Yes.
[00:01:16] Unknown:
Yes. And the one by a polynomial equation with certain restrictions.
[00:01:21] Unknown:
The one that we care about is called sec p two fifty six k one. Yes. And it is y squared equals x to the third plus seven.
[00:01:33] Unknown:
Yes. That's the one we care about.
[00:01:36] Unknown:
At least as Bitcoiners. Sorry. Continue. Bitcoiners. Yes.
[00:01:40] Unknown:
And you guys kinda know what it looks like, but everything we do is on it relies on either adding points on the curve or, adding a point to itself, which is doubling the point. Right? So, like, everything is really essentially based on adding two points on the curve. And, I was I'm going through I am going through personally a textbook by Neil Cobblets, who I think invent it is not that he invented. I hate to invent was it invented or discovered in conversation? He put the words words what he discovered. But that he kind of discovered, the significance of elliptic curves for cryptography.
And they might have called them cobblets curves at some point in time. But so I'm finally on the chapter on elliptic curves of his book. Been going through it since we started the show. And, you know, you think about the conversations we've had so far, and they've been difficult. Right? Like, I think the one where we talked about groups was great, but it was hard for people. Like Yeah. I mean, my daughter is a math major, and she's not gonna see what a group is still for a couple of years. Like, they don't you just don't jump right into that stuff. But, one of the things I remember discussing was we don't know why it matters to call something a group, but we know that it does. We know that that, like, confers information on our on the thing we care about.
[00:03:19] Unknown:
And that information is the interaction between the elements of that group. Well, that's
[00:03:27] Unknown:
yeah. Yes. So, like, in the so I'm I'm reading the Cobblets book. I get to his chapter on elliptic curves. And in the first paragraph, he says the points on an elliptic curve. Right? So imagine you draw it out, in your x y, you know, your x y graph. Your points x and y that are on that lie on the elliptic curve, if you take all of them together, they form a group. This is what I read. And I'm like, woah, this matters. Right? This relates. So here here we are now. Something is now called a group, and it's important that I know it's called a group, and the question is why. Right?
And so, if I go back to then the axioms of the group, right? The first one, and by the way, it's under an operation. And in the operation of elliptic curves, we know is addition is the one that we use. So we're gonna say, okay. So it's a group under the operation of addition. And the first axiom was that was called closure, which meant that any two elements in the group that add that are added together results in something that's also in the group. So in the case of the elliptic curve, any point, any two points on the curve that you add to each other is also a point on the curve.
[00:04:54] Unknown:
Right.
[00:04:55] Unknown:
That is powerful. So we're gonna kinda, like, take a step back for a second and internalize that. Well, it means that we can do these operations
[00:05:04] Unknown:
without going outside the bounds. Right? So like these group, like the, the closure of it is because there's like, if you can think of it as a physical structure, right? Like a group of things, you can't, you, you can't go outside of this. It's, it's closed. It's completely closed. You can't go outside of it using this operation, this operation specifically being addition. So anytime you add a point on the sec on an elliptic curve to another point on the same curve, you will fall within the curve still.
[00:05:37] Unknown:
Yeah. Which that that is like, if you look at maybe other types of, other types of linear like lines that you might or curves that you might be familiar with. Right? Mhmm. That's not a common feature. Right? So if I took the the line y equals x, which is like a diagonal line through the origin. Mhmm. Y equals x. So you have the point zero zero. You have the point one one two two three three. Yeah. Negative one negative one. Right? You take that line. Right? Well, the only way, well, that that you would have. I think you'd have closure on that line. I think any two points added together on that line are on that line. So I think that is like a rare probably a rare example.
Maybe maybe it's not. Maybe it's a com maybe that's actually pretty common. I have to do the math. I'm more you know, I have to do the math on that. But maybe any two points on the line are on that line, and that is kind of interesting too. Right? But so we have the so and that's maybe why it you know, I don't wanna get too far down that rabbit hole, but the t and the elliptic curve for people who have you know, part of when we do this when we started doing this show, we were thinking about people who maybe have some experience in cryptography but don't understand the math. And I think anyone who has experience in cryptography knows that we add points on the curve, and it's very important to know that the result is also on the curve. We're dealing with points on the curve. Right?
So, like,
[00:07:14] Unknown:
that is That's even that's how you can check, like, no. Hold on. Where was I going with that? Like, you can check that a point is on the curve. Never mind. I'm sorry. I was I was you you just evaluate the equation to check that the point's on the curve. Like, you can you can val I guess what I was getting at is, like, you can validate this. If you do x plus y equals whatever this is, you can go plug that result into this equation of the curve itself and validate that you are, in fact, back on it or still on it, rather.
[00:07:50] Unknown:
Yeah. That's right. Now adding points on the curve visually is not like, it doesn't look like doesn't look the same as you would do on a on, like, a u on a Euclidean line. Right? You I'm sure there's a a video we can find to that goes through all that goes through all that. But I thought it was really I don't know. It really was amazing to me to see those words to, you know, to see Cobblets find it important to say, oh, the points form a group. So, again, this is gonna matter. Like, the knowledge that the points on the elliptic curve are a group is going to matter. We don't exactly know why. Right?
Yeah. We just know that it matters to be able to call something a group. So I just I wanted to go back to that. So sorry to anyone who, like, thought that episode was particularly painful. But, like Well this stuff is gonna like, this is how the story gets weaved together.
[00:08:50] Unknown:
And to try to reiterate what these axioms were. Right? The the first was closure, which, you know, a and b, If you do those operations together, you get c, which is also in the group still. Yep. The second is associative, meaning you can multiply a or you can do the operation. Right? In this case, addition. You can do the operation in any sort of, like, grouping order. So whether you do a and b first or b and c first,
[00:09:17] Unknown:
it doesn't matter when you then go do the three elements. B and c. So in other words, you have three, let's say, three elements. Right. Whichever two you choose first doesn't matter.
[00:09:28] Unknown:
You're still within the group.
[00:09:30] Unknown:
Yep. And then the the last is the the neutral element. So there's an element of of one. I like the identity is the name for that element. Identity element. Yeah. Actually, sorry. So so in in under addition, it's zero. Under multiplication, it's one.
[00:09:48] Unknown:
And is that the
[00:09:51] Unknown:
I'm trying to remember back. Is that the infinity point or the So in the elliptic curve, that's right. That's right. And that and and the under the elliptic curve, I like, I know from, say, Jimmy Song's programming Bitcoin textbook that there's an there's something you call an infinity point. I never really it seemed like either a zero or something like that, but it was never really clear what it was there to sort of make it all work, but it wasn't really clear why it was needed. Now it's like, okay. So now we also know there's an identity element of that group, and we they call it the infinity point.
[00:10:28] Unknown:
Right.
[00:10:29] Unknown:
But in a general group of addition, it's zero.
[00:10:33] Unknown:
And the property of this is that in that identity element times any other element gets or I'm sorry. Yes. Plus plus plus. The identity element Yeah. Plus
[00:10:47] Unknown:
any other element in the group gives you the same element back. Yeah. In other words, a plus the identity element equals a. Anything plus the identity and and the identity element equals itself.
[00:10:58] Unknown:
Right. And there is a an inverse of a. That's right. Right. So if a is an element in this group, there's an inverse and you can take a plus its inverse, and you get the identity element.
[00:11:13] Unknown:
That's right. And so in addition, it's negative. It's the it's the negative or with the opposite. Right?
[00:11:22] Unknown:
Yeah. That's always the inverse and then of addition is negative. When you'll see the inverse represented as a to the negative one power?
[00:11:32] Unknown:
Sometimes. Yes. Which, again, you see a lot of notation that is assumes multiplication. That's how you would think about multiplication. Right? But when you're dealing with groups generally, you might see that notation even though it's even though the operation isn't necessarily multiplication. But you still might see it, you know, you might see it written that way. Right? Yeah. So the inverse of an element in a group that's using the operation of addition is just always the negative of that number.
[00:12:05] Unknown:
One and I came across the, one of the reasons why like, one of these theorems. So in the understanding cryptography PDF, there's Fermat's little theorem. Right? Yeah. Which is basically element a
[00:12:21] Unknown:
raised to Sorry. Sorry. Sorry. Before you move on, I I can feel it. Yeah. I can feel we're moving on to another track real quick. I just wanted to go back and say, by the way, it wasn't just a group that the points represent. They represent they're actually an an abelian group, which means that it has the additional property of commutativeness which means that the order, like, the the order of, the left and rightness of the of multiplying them. Sorry. Right. The left and rightness of adding them doesn't matter. Meaning a plus b equals b plus a, which sounds obvious. Why did I just spend a minute even discussing that? But abelian groups have special properties too and I think we will find out why it matters with elliptic curves.
So I wanted to just get that out for completeness because I know we're about to move into something else.
[00:13:14] Unknown:
One and again, just to, like, really complete so closure, associativity, identity, inverse
[00:13:22] Unknown:
Yep. And communicative are like the five. Is not an axiom, though. No. It is a feeling group. It's a potential additional property of a group. But you don't a group it's kind of like, you know, like a quadrilateral is a can be a rectangle, but a rectangle isn't always a quadrilateral. Or a square is always a rectangle, but a rectangle isn't always a square. Right. Okay. Right? So a group can be abelian. Abelian group is always always meets the four axioms, but meeting those four axioms doesn't mean you're
[00:13:59] Unknown:
Abelian. Abelian.
[00:14:00] Unknown:
But under addition, typically, addition is typically always in a sort of a feature, always has that property typically. Subtraction doesn't. So, like, anyone can now take a pen and paper, and they can see for themselves that subtraction is not if that's the operation, if that's not a b like, it matters. It does. Yeah. Yeah. Five. What's first. Right? Yeah. Five minus two is not two minus five. Right. Right. Right. Right. You can see that. So it's not always the case, but we know for elliptic curves, it is the case.
[00:14:35] Unknown:
Under addition? That's right. The the identity piece of groups or, not the identity. The inverse piece of groups Yes. For Matt's little theorem.
[00:14:49] Unknown:
Yeah. Okay. Yeah. Now I see where you go. A is an integer
[00:14:53] Unknown:
and p is a prime number, then a raised to the power of p is congruent, which we covered this before. It's like it's like not equal, but it's like the same ish.
[00:15:06] Unknown:
Yeah. When I'm using mod. Let's let's just load up an actual example. Maybe p is five. Okay. Right. And you so because we've done this in the past. And let's just quickly Yeah. Yeah. Go through the number two. Right? Two raised to the one is two. So two can generate the entire group. Right? Yeah. Two two raised to the one is two. Two raised to the two is four. Four. Right? Two raised to the third power is eight, but mod five is three. Yep. So two to two is now so we've generated two, four, and three.
[00:15:42] Unknown:
Right? Yep.
[00:15:43] Unknown:
And, next is 16. Right? Two to the fourth power is 16, which is actually one. So now it took you to the fourth power. Two to the fourth power turned out to be the identity. Two to the fourth power gave you the identity, which is one. Right? The multi and this is all under multiplication now. Right? This this is now all under multiplication. So two to the fourth power in mod five is one. K. Four is five minus one. Okay. And any multiple of four, I bet you, any multiple of four, if you raise two to that power, will give you one in the mod five. You wanna try it with two to the eighth?
Let's try it with two to the eighth. Two forty eight. Two Two thirty two sixty four. Two fifty six. One twenty two fifty six. Yes. So two fifty six is clearly one mod five. Right? I don't know. I have to do that, guys. And I guarantee and so the power of this is that you know that two to the eightieth is gonna be one mod five, which means if I said if I asked you what's two to the eighty first power, then it's two to the eightieth times two. Two to the eightieth is one. So I can tell you quickly two to the eighty first power mod five. The answer is two. Alright. Let's let's go over that one again. Oh, okay. This might be my first video that I that I that I do for this group. Okay? Yeah. Yeah. Yeah. Yeah. I'm gonna do two to the eighty first power by hand and prove to you that the answer is two.
Okay? Because this is the power of Fermat's little theorem is that you can you have this knowledge that two to a power that's a multiple of one less your prime. Right? You back one off your prime. So your prime is five. You back one off and you now have four. So two to the fourth power is one and you go through this cycle. Right? You go through five, six, seven, eight, and you get one again. You do nine, ten, 11, 12. I'll do this in a video. You get one again. Oh, okay. Yeah. Yeah. Yeah. It's just so every four times you multiply two by itself, this element, it's because that's the two's called the generator. Anytime you have this generator and you, in in a prime field, that's it's it works beautifully.
So I could tell you that I mean, you pick any number. Literally. Literally. Get pick any tell me a three digit number right now. 173. Okay. Two to the +1 power. Okay. Yeah. I I can tell you right now is the same as let's see. It's so it's every four. What's 173 divided by four? I should have brought my calculator with me to this podcast. So let me do it real quick. Okay. So one seventy two to the one seventy two equals one. So that's gonna lead I know the answer is two. So write that just write that down and text it to me so I can demonstrate that in a video. Alright. I'll text it. The one hundred seventy third power. I know it's gonna be and and and a mod five.
So I hope like, what I think is happening right now is what Fermat's little theorem did for me is showed me how, it's possible to really multiply the power of modulo and the power of remainders enables us to start to do arithmetic with really, really, really, really big numbers. And numbers so big, this is part of what we were talking about before we started rolling. Like, at some point, you're going to be doing arithmetic with such big numbers that there's no way in your lifetime you can even check yourself. So this is why it's, like, important to understand on the ground you stand on, at least, how to do this with what you can see and prove now. Like, in other words, two to one two to the hundred and seventy third power is nothing compared to what goes on in public key cryptography.
You know? Like, it's nothing. It's really tiny tiny number.
[00:19:56] Unknown:
What brought me to this Fermat's theorem is we were talking about the properties, and it and it says that one of the uses, one application of this theorem is computation
[00:20:06] Unknown:
of the inverse in a finite field. Yes. And this is in programming Bitcoin, by the way. That the first time I ever heard of Fermat that there was something called Fermat's little theorem was reading the book programming Bitcoin. And I probably talk about this book every episode here because Right. It's the thing that kinda woke me up to the fact that there's this I didn't even know there was this man. Right? But that I mean, I I don't know about you guys. That kinda blows me away that I can I you know, one of the greatest things you can do in math is eliminate a giant portion of what you're trying to of what you're trying to calculate? Yeah. Copy computational shortcuts. Two to the one seventy three, and you know that two to the one seventy two is one. And you just put a big slash through that, and you're left with that times two.
Right? That is incredibly powerful. And also from a cryptography perspective, I think it should put fear in us to say we have to be really careful about if it's that easy to reduce certain numbers. Right? We gotta be careful and make sure we're not that we're not dealing with Fermat numbers in with our secrets. Right?
[00:21:24] Unknown:
Yeah. Because you don't want them to be reducible.
[00:21:28] Unknown:
Correct. Like the whole point is to say, well, the whole point of what we're doing in cryptography is to take all of those tools out of the hands of people who would try to guess our secrets. Right? And then say that's the only way there. The only way you're getting Just by guessing. You're getting into my door is by being a a lucky idiot. Right? There's not you can't there's not like like, there's nothing you can do on this world Yeah. To, eliminate a single arithmetic operation, my friend. And that's so, you you know, Fermat's little theorem is really powerful. Really, really powerful, and I can't stress it enough. I think that I like, it's I am going I'm determined to do a good video for you guys. On for Matt's little theorem? On this. Yeah. And that's like and and it was saying in here too that it was for Matt's little theorem is is
[00:22:24] Unknown:
just almost like a special case of Euler's theorem.
[00:22:27] Unknown:
Yeah. And that's what I knew. When you started texting me last week that you were gonna you're looking at Euler's number, I was like, okay. For Matt's little theorem, it's got to be
[00:22:36] Unknown:
Oh, is that how you say it? Oil e u l e r spoiler.
[00:22:40] Unknown:
I don't know. I mean, it's still funny, dude. This is the second time you got the same phonetic. I I used to say that too. I used to say you Yeah. To me, it's Euler. Euler. You You know? Oh, this is not an English podcast. It's Ferris Euler's Day Off. Yeah. Exactly. For me, that's how I heard it. You know? And I think I was corrected again. This is the second three. I think we did it I think we got there with Galois too. It's like I was walking around going to Golois and all this stuff and
[00:23:06] Unknown:
Galois. Okay. So it's not Golois. It's not Euler. It's Galois and Euler.
[00:23:12] Unknown:
I think that's how I heard the highly regarded people who inform our knowledge system say these things. Alright. Alright. That's what I all I could say. So for Matt's little theorem is really powerful, and I I guess what I wanna clarify here is it's it's specifically when your modulo is prime. Right. And because when I don't I think it's too much of a leap to get to Euler, to be honest. And I mean, I'd almost rather not do it. Just I I I think it it or maybe we get to it by the end of this episode, but I think it's important to understand that, if if you have a prime number like five, right, what you wanna what what is the field generated, right, by that, like, by that modulus. Mhmm.
Anytime the modulus is prime, there's a a group it's called an Euler group. But, it's all of what is the group that has basically all of the numbers quote unquote this okay. I haven't we haven't talked about co prime. We haven't talked about greatest common divisors. We haven't we haven't talked about real I think we touched on greatest common divisors. Relatively prime? Did we discuss relatively prime? No. We didn't, but I had a highlight in here,
[00:24:40] Unknown:
for Matt's little theorem. And it it it said, the theorem is helpful for primality testing and in many other aspects of public key cryptography. But for whatever reason, when I read that word primality, my mind went to, like, primal as in, like, the idea of, like, things that are, like, fundamentally,
[00:24:58] Unknown:
like, buried deep within. Right? Like, when you think, like, primal instincts Double meaning. Some of these really do. Like, I always when I first heard of a discrete logarithm, I thought it was discrete like secret. Yeah. Like a natural logarithm. Not to but and I think it has I love it. I love it. It has, like, a double meaning because discrete really is that it's non continuous. Yeah. So I I, anyway, so let's talk quickly about what it means for two numbers to be, relatively prime. We know what it means for one number to be prime. Correct? We know that it the number that who that has no factors other than, like, itself and the number one. Yeah. Right?
So if I said There are no
[00:25:42] Unknown:
let me let me try to, like, say this a different way. Any other yeah. Yeah. There's there's no numbers less than itself that can be combined together to give you this number. Right. So, like, seven is an example, and this is, strictly speaking, multiplication.
[00:26:02] Unknown:
Right? Like, so It should say no real numbers. That's no. Nothing Yes. Nothing, because you can actually find complex numbers that do this. So it's what? Three, five, seven, thirteen, like, are, like, the Two two two is also 2. 2. Yes. So 2357.
[00:26:19] Unknown:
2 3 5 7. 11 13 7. 11. 19. And that's just because there's no numbers that you can multiply to get to. Yeah. No real numbers that you can multiply to get to that number.
[00:26:30] Unknown:
Now this is easy to do, pretty easy to do if they're if under 50. Under a hundred, you need a little bit of time stable experience probably. But when you start to get to numbers that are five digits long, like, if I said 10,001, does anybody know if that number is prime or not? You're gonna just get in your calculator and start trying shit. Right?
[00:26:54] Unknown:
Until you Was any number ending in one prime though?
[00:26:57] Unknown:
Sure. Any number ending in one? 30 one. 40 one. Right. Yeah. Those are prime. Right? Yeah. I mean, plenty of numbers ending in one could be prime. Right? Yeah. Yeah. Yeah. My point is, yeah. So, like, for 10 a number like 10,001, the like, primality testing is, like, a lot of what we talked about how much arithmetic I do. A lot of it is just doing some of these primality testing algorithms by hand. Mhmm. Because and they're they're interesting. Because basic they're more, they're more powerful and more effective than just the brute force of plugging numbers in and seeing if you get another integer. Right? Because that's what you'll do with 10,001. You'll plug 3. Maybe you know it's not 3, but you'll plug in 7, and then you'll plug in 11. And you'll go up to the square root of 10,000. You'll go up to basically a hundred.
[00:27:55] Unknown:
Right? Yeah.
[00:27:56] Unknown:
That's all you have to do. And then you'll figure out if that so but, you know, that could take a really long time. What if I said a million and one? What if I said a billion and one? I mean, it's gonna it's you know, it starts to take a really long time to To go through the To do all that. That's so it's just a so let's go back to, primes. Right. K. Just regular prong, stuff we know. Number five, seven, you know, 11. Now there's this concept of two numbers being relatively prime. And what that means is that so technically it means their greatest common divisor is one.
But intuitively intuitively, it just means that there's no they don't share a common factor. So if I took the number six and twelve, obviously, you can see that they share a factor and they're not, Those are not relatively prime to each other. Right? Nine and twelve are not relatively prime to each other. You can see that they had shared the three. Three. Yeah. Right? But, like, nine and seventeen are relatively prime to each other. I think probably I'm trying to think of two numbers that aren't prime. Right? Like, ten and twenty one.
Right? 10 is five times two. 20 one is seven times three. They share no common factor. So those are relatively prime.
[00:29:29] Unknown:
Okay.
[00:29:31] Unknown:
Okay.
[00:29:32] Unknown:
Why does that matter?
[00:29:33] Unknown:
Yeah. Good question. So that's the always the next question. Why does that matter? Okay. So let's sit on that. Let's sit on that. Always have that question in our mind. Right? But Mhmm. But we're not gonna stop because we don't have a great answer. We just, like it's almost the flip side of that question is, like, it's not like why does this matter? It's more like, oh, in a curious way. Can you do with this? Wonder why this matters. Okay. Yeah. Yeah. So let's just keep that until until the light bulb goes off. Right? So now when you go and we talked about creating a group that's modulus a number, like five. And that number was that group consisted or that finite field consisted of numbers the numbers one, two, three, and four.
Right. Right?
[00:30:22] Unknown:
Yep.
[00:30:24] Unknown:
Because, they are you can generate a field, that is, the members are relatively prime to the modulus, to the thing you're dividing out. And when in that number is prime, it's always going to be all of the numbers prior to that number. So So I'd say that you can you can create In other words, because one, two, three, and four are all relatively prime to five. And that's the same is gonna be true of seven. The same is gonna be true of 11. Right? Let the the field of numbers relatively prime to 11 is always gonna be the digits. All the numbers. Zero to you know, all the numbers through 10.
[00:31:11] Unknown:
Oh, because a prime number itself, like anything less than a prime number, is just relatively prime to it by default because it's a prime. That's why it is a prime number. So that's what makes primes
[00:31:21] Unknown:
special that you could generate a field. And this is literally page one of the book Programming Bitcoin. It went way over my head. I didn't understand. Okay. I'll just go revisit that one again. This is on page one of that book. Not to shell that book too much, but I've that's Yeah. Worth that book is worth promoting because of because of how good Because of the entry point. Yes. And it it brings to bear all of these things, and you don't have to know any math to, like, go through the book. But, like You don't because I skipped over all that stuff and went right to just programming it. But it all wakes up when you start to see okay. Yes. You can generate a finite field modulo a prime, and that's gonna give you all of the digits less than that prime.
[00:32:07] Unknown:
You're right. Right?
[00:32:09] Unknown:
Okay. And so now what happens the question is what happens when your modulus is not prime? Okay. So let's say we wanna generate a group modulo nine.
[00:32:25] Unknown:
Yeah.
[00:32:25] Unknown:
Now, let so let me take and and and the group's going to be all the numbers relatively prime to nine. And I'm going to just do this in my head that it's going to be the number one, number two, not three. Right. Yet. Right. Yes to four. Yes to five.
[00:32:48] Unknown:
No to six. Not six.
[00:32:50] Unknown:
Right? Yes to seven, yes to eight. I should have picked a better one. But, let's do 10. Okay. Okay. Let's do an even let's do 10. So yes to 1. It's 10. We have +1, 379. When's your first numbers? Again. So noted obviously, all the even numbers are no's. Right? And 5 is a no. Right. So we have +1, 379. Okay. Okay. And guess what? So you talked about you talked about the Euler number. The Euler number is the number of elements relatively prime to that number. So in other words, the Euler number of 10 is is the number of elements before 10 relatively prime to 10, which is four.
Now, keep the number four in your keep the number four alive right now real quick because Yeah. What we're gonna do is pick an element of that group. Call it three. K. Okay. Okay. Three to the first power is three. Yep. Alright. Three squared is nine. Remember our group, one three seven nine. So we've now three squared. We're gonna generate this group. Okay. And we're gonna figure out when we get back to one. K? We're gonna Okay. Take try so three squares modding by 10? Modding by 10. Okay. I feel very lucky because I picked a great number to mod by. It's very easy to mod by. Three third is 27. 20 seven. So that's seven. Right? So we've generated Yeah. So we've generated three, nine, and seven so far. Right?
Which which element are we missing? We're missing one. So let's hope three to the fourth, which is 81, there's our one. So now, like the so it's like this analog to Fermat's little theorem. Fermat's little theorem, it was always prime less one. Yeah. But it just so happens that that is the number of relatively prime elements to that prime. So Euler generalized it. You know, Fermat was not even a mathematician. Fermat was a lawyer who just spent every waking hour doing these calculations in his head, and he was a fucking genius. Right? But Euler So basically Yeah. Euler generalize this.
[00:35:17] Unknown:
The elements in a group mod whatever. Right? Mod a number. Is my subgroup? Of co prime numbers in that group.
[00:35:31] Unknown:
Yeah.
[00:35:32] Unknown:
If you take any element in the group and and raise it to the power of the number of co primes there are. That's the power that makes you makes it one. Yes. Then you get one.
[00:35:42] Unknown:
It assuming you that's a generator. Yes. That's assuming, like, that number is a generator. Right. And and when we say one, it's like We got lucky that three is a general I mean, I we could test it out with the other elements in the group. I don't know if they're all I don't know if they all are. I think they are. What's 7? So we can do 7. So 7 to 1. Just 7. 7. 7 here it is. 49 is nine. 40 nine is nine. Three. Yep. And then what is seven to the fourth? I think the mod is 9 on that. I'm not Seven to the fourth is 2401. Oh, boom. Mod 10 is one. Yeah. So there you go. So seven also generates all four elements of the group.
So now this is even more powerful than Fermat's Little Theorem. If I said, what is, in mod 10, what is seven to the, you know, eight thousand nine hundred and sixty eighth power? Right? I just have to figure out where the four, how far the so eight, nine, six, eight. That's actually evenly divides four. That's one. So I know that nine to the eight thousand nine hundred and sixty eighth power, modulo 10, the answer is one. Magic.
[00:36:51] Unknown:
Any multiple
[00:36:52] Unknown:
divides four. Yeah. That's right. So add add to the power of any multiple of four because modulo 10, there are four co prime elements. Right? So it worked for Fermat's. Fermat's little theorem is so cool because you don't have to think about co prime. It it is true that the prime minus one is the number of co prime elements. And you don't have to Because otherwise, you're gonna have to calculate all these co primes to get that number. So for modulus of the number, it allows to, like, boil this down only for prime modulus. Yes. It it's really easy to understand for primes. Euler basically allows you to do this for any number.
Right? You can say, well, it's raised to the Euler number, which for a prime is prime is that prime minus one. Pretty fucking cool. These are the videos I'm going to make, and it's okay if they suck, people. These videos suck, but it's gonna be cool to walk you through this. I really really want to do this. You'll find those on on Oster only.
[00:37:55] Unknown:
The end file will be in the show notes. Well, maybe somewhere else, but
[00:37:59] Unknown:
I'm definitely not sure. YouTube channel for this.
[00:38:02] Unknown:
Yeah. That's all. YouTube, Rumble, all of them. Put them everywhere.
[00:38:09] Unknown:
So that was an inch I mean, Jesus Christ. I I hope that wasn't too obtuse for people. Right? Well, let's see if we can try it. Fundamental things. These are really fundamental concepts of at least cryptography. And like I said, we're talking pay like, we're talking chapter one of programming Bitcoin. Mhmm. You'll find you will find all of these things. So, you know, if you can find yourself that book somehow, I would definitely check out, like, yeah, check out the first chapter. Available online as a PDF. K. Good. Yeah. And I think it's on the GitHub too. Like, I think you can go on on their GitHub, which I'll link to the show notes again. Fermat's little theorem, Euler's number, and this is really how this is part of how you calculate so when you're doing elliptic curve, this goes back to when you're trying to add two points on an elliptic curve. Maybe I'm heading for white water here. Maybe I really screwed up. But I think that I do think that somehow this is used in calculating the inverse, on the elliptic curve. It is. Yeah. Modulo that prime. Yeah. But then why is an inverse important?
[00:39:27] Unknown:
Right? Like, why is being able to calculate that inverse important?
[00:39:32] Unknown:
Yeah. We'll get there. Okay. We'll get there. Right? But it it it seems intuitive just like two dudes talking about Fermat's Little Theorem. It seems intuitive that being able to calculate an inverse, particularly the the one that equals one, especially if that scales to all out to, like, all of the exponents that are,
[00:39:57] Unknown:
you know, that have a certain Yeah. It doesn't matter if it's a certain multiplicity
[00:40:01] Unknown:
that it's very powerful to be able to eliminate, you know, just eliminate a portion of your calculation.
[00:40:08] Unknown:
And correct me if I'm wrong, and maybe this is me gonna try to divide. I'm sorry. So, like, in inverse is called is also division.
[00:40:14] Unknown:
The same way subtraction Well, subtraction. Yeah. You Division. Add the inverse. You're subtracting. Yeah.
[00:40:19] Unknown:
So if when you when you wanna when you wanna subtract something and you only have addition available Mhmm. You can just add whatever the inverse is. And isn't that what the elliptic curve point addition uses? Is it like you end up adding and then taking the inverse of whatever that answer is?
[00:40:39] Unknown:
Yeah. I I we'll hold on. Go there. We'll not go there. I'm not confident enough. I feel like I've already stepped in a bear trap because I'm not clear on how we get from addition in elliptic curves to what we're talking about, which is happening in the multiplication space.
[00:40:56] Unknown:
Well, multiplication is That's not clear. Just adding over and over again. Right? Like, three times six No. No. Yeah. Six plus six plus six.
[00:41:05] Unknown:
This this idea of of no. Yeah. I understand. But now we're Mhmm. We're we're we're in multiplication, you're using powers to essentially do the same thing, and so it's a different operation. And I think it's probably because it I don't wanna get I don't wanna get too much into it, but it goes back to a you know, it's also it it's also a ring. A field is a ring that contains both addition and multiplication and allows for both operations. And I'm guessing that is I'm guessing we're killing people right now too. But, like Well, that's fine. We'll get there.
[00:41:40] Unknown:
I was looking you know, the next sort of, like, part of this this PDF that I was gonna look into is, like, okay. It goes into RSA, but I don't I don't, like, I'm gonna skip that. And that's a great motivator. RSA is a great motivator
[00:41:53] Unknown:
for the stack that I continue to, like, say is, prime numbers, Euclidean algorithm, division algorithm, algorithm, Chinese remainder theorem, Euler's number, Diophantine equations. This is a stack that we I wanna, like, get to all that's a number theory stack that gets you essentially to public key cryptography to to discrete logarithms.
[00:42:17] Unknown:
Right. And that's the next sort well, that's not the next piece in the book. If I skip over the RSA chapter, it's Diffie Hellman key exchange.
[00:42:27] Unknown:
Yeah. And I I'm happy to continue to just read this table of contents every episode because it's it's like how you guys will see it in a book and say, okay, I've seen enough people mention these things together that this is probably, you know, an important thing to learn.
[00:42:44] Unknown:
Well, it calls out so in the introduction to public key cryptography, it calls out essential number theory for public key cryptography, Euclidean algorithm, extended Euclidean algorithm, Euler's five function, Fermat's Little Theorem, and or Euler's theorem, which we've gone over all of those at this point.
[00:43:03] Unknown:
We've touched on them. We've touched. So and I think it's worthwhile I'm looking at time. I think this is good. We can I think we can articulate a little bit about public key cryptography and what goes on and how that just expanding on what we've done in the last forty minutes? For those of you who have stuck with us, God bless you guys. Public key cryptography. And I mean, you guys know this, right? And like, Gary, you know this because we just, you tell me, you were telling me this, right? But like the Diffie Hellman key exchange is based on two basically, two prime numbers that multiply out to a big number. Right?
Called a big number and and in the public space, everybody can know that number. Right? Yeah. Now, you know your component.
[00:43:57] Unknown:
Well, that that
[00:43:58] Unknown:
number is is probably referred to Hold on. So n is the is the is the combination of a times b. Both big numbers. You know a and I know b. Yeah.
[00:44:10] Unknown:
Right? Yep.
[00:44:13] Unknown:
And they're I don't know, like, I in fact, so, yeah, we know we we all know we all know our piece, and I don't wanna fuck this up too much. Why don't you go you know, I don't wanna fuck this up too much, but, like, it's basically based on you knowing the full number cannot back you into either the two numbers. Right? And that that's the nature of a discrete logarithm. You can't it's too hard to back into the two numbers that multiply out to that big number, and it can only be done by root force.
[00:44:47] Unknown:
Yeah. There's it it it's essentially there's a publicly known large number that both parties are then combining separately. And when you exchange those numbers, you're able to derive a common secret. Yeah. That's right. Or a common you're you're able to arrive at the same answer that can then be used as a common secret. Right? So one of the things is, at least in like software applications, you use Diffie Hellman when you're exchanging keys over the Internet to then have a shared key. Right? So a lot of symmetric ciphers, meaning the same key encrypts and decrypts, like that's a very efficient thing for computation.
And so it's used a lot for encryption on the Internet. Right? When you get your little lock icon, your SSL lock icon, that's that's because you and the server have done a Diffie Hellman key exchange, and now you have this thing called it's, you know, it's like a session ID or a session token, but it's essentially a shared, and that session ID or token might not be the exact thing, but it's there's a shared piece of data. There's a shared secret now that both parties are privy to that enable you to encrypt and decrypt in an efficient manner. But there's no exposing of that secret on either side. You're just exchanging public values. Right.
And then using the math too. So my secret and your secret, we combine it with this public value. And then by also again combining once I give you so you have x, I have y, and we have this public value of a. Right? I take a and raise it to x. You take a and raise it to y. Yep. And then we exchange those. Right? And now I don't know what your power was that you raised it to, But I can take the outcome of that and raise that to x
[00:46:40] Unknown:
and you or, to y This is look. So the way I always the only way I learned about this is from enlightening. And, like, when you so when you open up a lightning channel with somebody
[00:46:53] Unknown:
Yeah.
[00:46:54] Unknown:
And you're trying or even when you're trying to find a route to somebody. Right? Everybody is basically trying to, nobody really knows if the message is meant for them. But if you're, you know, if this process fails, then you know that this you're just a you're just a hop. Right? If this process succeeds, then you know that the payment is made for you. You know the message is made for you. Right? Yep. And that's without and that's how the two people know without ever sharing their secrets, but you they know the big number. Suggestions. I'm not sure what's yeah. Is that a video? You had a video going on there? It was a video. Yeah. And it was there's actually a great video on,
[00:47:38] Unknown:
Diffie Hellman key exchange from this guy
[00:47:40] Unknown:
that is Let's put this in the show notes for sure. Computer file.
[00:47:44] Unknown:
But it uses color mixing to sort of explain it. Right?
[00:47:48] Unknown:
Oh, yeah. I've seen this. This is great. Yes. I've seen it.
[00:47:51] Unknown:
Yeah. So if I have a color and you have a color and then there's like a shared color, if I combine my color with a shared color, you combine your color with a shared color, and then we exchange those two, we will arrive at the same color by, again, adding our color back into it on the piece that we exchanged. And so that is that's what this, like, this this video that he does. I found that he's been this Computerphile
[00:48:15] Unknown:
channel is great for sort of, like, explaining things. Yeah. Now if you exchange a number with somebody and that person is smart enough to know that it's prime. Right? Yeah. Yeah. They can back in to your secret. Right? So that's why it's so important that these numbers are so big that not even the primality testing algorithms that we know of are ever gonna be able to break them down. And, like, you're never gonna know that their number is they'll never know if their number is prime. Although, I don't I might have just stepped in shit again, but, like, you know, it it's that that that I'm this is the idea, though, of, like Well, it's because the why we use big it's why we use big numbers. And, you know, for Matt's little theorem, it does allow you to really buzz saw into a large number if you happen to know that it's raised to a you know, if you know the modulo, which we do in Bitcoin, it's gigantic.
[00:49:20] Unknown:
Right? Right. The generate pointer is known. Yeah. But that that generate report is co prime to all the other
[00:49:30] Unknown:
points. Has to be. You can't be. Yeah. Must be. And that's why the like, when we talked about that group modulo 10. Right? Yeah. It's the unit group is called, and these are all the numbers co prime to 10. Those are all basically, those are all the generators of that group too.
[00:49:47] Unknown:
Right.
[00:49:48] Unknown:
Right? Right. You have to be and there's a, like, there's a lot of very tedious theorems that prove all this that I don't think I really recommend. I think this is the good level to just understand that being co prime to the modulus makes you actually a generator now of that group. So one one five except well, you know, not one, but three, five, and sorry. Three, seven, and 10 were were generators. Three, seven, and 10 were generators of that group.
[00:50:25] Unknown:
Well and and I think if we if we if we go back to, I think, our first episode while we were talk you were giving us a story on why this is important to you because you got to these, like, giant numbers in the sec p two v six k one, and you were like, what is why what does this even mean? I saw a wall of numbers. Yes. I saw a wall of hardcoded numbers and not formulas and just panicked.
[00:50:48] Unknown:
Well, but I I think I think I know what they are.
[00:50:52] Unknown:
Understanding this one aspect of the generator point is co prime to all the other points on the elliptic curve is like a critical thing because it it does not allow because there there are no shared factors, it doesn't allow you to, like, back into the number.
[00:51:11] Unknown:
I don't know that they're co prime to all the other points. I think that but they're co prime to the modulus.
[00:51:20] Unknown:
In other words Oh, the generate yeah. You're right. The generator is not the modulus.
[00:51:24] Unknown:
Like, 35 sorry. 37 and 1379 are 39 are not co prime, but they're in this group because they're both co prime to 10. Right. People. Using yeah. Yeah. This is They're not co prime to each other. The points are not co prime to each other necessarily. Correct. They're co prime to the modulus, and therefore, they're generate that makes them generators of the group. But using a group
[00:51:49] Unknown:
mod a nonprime number. That's what I'm getting at. Using a group so when we use the the mod 10 example Yeah. Right? And we have those elements in there that are Yep. Like, not necessarily co prime to each other.
[00:52:03] Unknown:
They're co prime to 10.
[00:52:05] Unknown:
It is. Yes. But three and nine are not co prime to each other. What I'm saying is if we use 11, and that's a prime number, instead of using 10, now we have a guarantee that everything No.
[00:52:18] Unknown:
Because now you have all the numbers. Right? Two, four, six, and eight are all in that group, and they're not co prime to each other. They're never co prime to each other. You never have the, like, the groups the elements of that group are co prime to each other. You never have that.
[00:52:33] Unknown:
Right. And I think that's I think that's important though. Yeah.
[00:52:37] Unknown:
Okay. Yeah. Am I am I missing something there? I think we're all I I mean, we are I don't know. Okay. I don't know. This is a we're I think we're struggling we're struggling here probably the same way listeners are because we think it's like, you know, sometimes you think sometimes we think we're really on to something. And, like, for me, this is like I'm a musician and I can play, like, 85% of, like, a ton of songs and I start playing one and people start getting into it and then I hit a and then I forget. Like, oh my god. Wait. There's a whole point of the song. I don't know. And it's gonna be like, I'm gonna have to abruptly I'm gonna have to abruptly either try to pretend I know it or abruptly stop. You know what I mean? And I don't wanna get anything wrong here. Right? Yeah.
And so I think we kinda both started jamming on a song that we both knew 85% of and we hit a we hit a snag, you know. Well, this is the danger of us doing this. This is this is why I mean, this is a dangerous podcast for us. But But we're we're gonna we're gonna do it. We're gonna do this. We're gonna get we're you know, like, the discovery the upside of what we have to discover is so great that it's so worth it for me to do this here with you and to take this risk. Yeah. So I hope the listeners feel that way. I hope everyone who's gotten to this point, it's just like, yeah. Okay. I get it. Sometimes this fucking sucks. And I don't know, man. If you guys listen to this on, like, two x or three x, god bless you. I don't understand how to do it. Trying to get at was
[00:54:17] Unknown:
right. So so in elliptic curve cryptography, which is, like, the ultimate thing that we're trying to Yes. To truly understand here. There's a holy grail. We are using a prime modulus, right, to define
[00:54:31] Unknown:
I would think so. I would think so because then you otherwise, you have completely, sparse. Right? You know, the difference between using eleven and ten is the difference between having all 10 digits and having only four of them in your group. Right? Right. Right. Right. So it's it would make sense that the modulus would be always prime. So that you have a complete at least the complete group of integers less than that prime. Right?
[00:55:01] Unknown:
Now does yeah. I'm trying to think. So it because if if you if you're using, like, a mod 10 as your number, as your as your as your prime, order, Is it order when you're defining the field? Or I would just call it a modulus. A modulus 10. When you're using when you're using modulus 10, if you're not looking for this co prime to define your group, you're gonna run into issues of actually defining a group.
[00:55:34] Unknown:
Correct.
[00:55:36] Unknown:
Yeah.
[00:55:38] Unknown:
That's right.
[00:55:39] Unknown:
Okay. I'm just trying to, like, I'm trying to reason why why do you need a modulus of prime. Right? Why do you need a modulus of prime? I mean, it's I think it's let's just let's just stick with this discovery that
[00:55:50] Unknown:
it is a group. Like, those numbers form a group. The fact that one, three, seven, and nine actually form a group, and we can prove that too. We can say, look, three times seven is 21, and that's my one. Three times nine is 27. There's my seven. Like, all you can multiply every element in that group and get closure. Let's not take that for granted for for a second. Right? Yeah. Yeah. Yeah. That that it this is one of those things where we call the fact that you could even call a group is interesting.
[00:56:20] Unknown:
It is interesting. But again, getting back to, like, why prime to define the modulus for the group that you want? And I think having It's the same property, but you have all the numbers now. Now you have Right. Right. Right. Like a complete domain. You have a guarantee that everything underneath that number is is is part of the is an element in this group.
[00:56:39] Unknown:
And it would make it would make it much easier for an attacker to guess what's going on if he could eliminate three quarters of the domain.
[00:56:47] Unknown:
Exactly. Yes. That's what I was yes. Okay. Alright. So
[00:56:53] Unknown:
that's why I think the prime modulus, it seems to be I'm guessing, but, like, that seems to be why we would why that would be possible. A vast group. Right? Like Correct. The the the group is fast. Basically the most I don't wanna use terms that I should Huge. The most possible I think the largest possible domain, you know, when trying to guess, you know. Yeah. Could be wrong about that, but then again, it's just a guess. This is on this is where I am on the journey. All I can do is give you my best guesses right now.
[00:57:31] Unknown:
That's I mean, that's all anybody can do, right, is is explore, do the do the math,
[00:57:37] Unknown:
do more math. There are cryptographic schemes that randomize the modulus so that you don't know what a valid number is even to guess. Like, that would be kind of a that's possible too. I don't think that's the case for Bitcoin, but I do think that's potential that it would make sense to me for a general cryptographic scheme as well. Right? Where you ran you just flip around, like, your secret is the modulus potentially. And I don't but I I don't know how that would work. But it would make sense that you wouldn't even know how to guess. It would be very hard to attack that. Right? Because you'd be doing a lot of try a lot of thud tries because you're guessing numbers that aren't even in the group.
[00:58:20] Unknown:
Yeah. It allows you
[00:58:25] Unknown:
But in Bitcoin, we it's it's a where the modulus is a prime even though there there's no way to prove it. There's no way any of us can prove it.
[00:58:33] Unknown:
Prove what? That it's a prime? Yeah. Because to go through without using
[00:58:39] Unknown:
It's too big. These yeah. It's too it's too big to brute force because otherwise, you're just brute forcing everything. It's very hard to prove a number. It's very easy to prove a number is not a prime. You find a number that divides into it and eventually if like, basically, what what what it ends up is is it becomes a probabilistic exercise where you say, well, I am comfortable within point 001%. You know, I'm 99.999% confident because I've guessed such a large portion of the potential numbers it could be that no number I haven't found a number that divides into it yet. Right? But I don't have time on earth to test every number there is to see if it's a factor of this big 50 digit number. Right?
[00:59:27] Unknown:
So all you can do is say You can't do a holistic complete proof is what you're saying. You can't There's no way to exhaustively
[00:59:34] Unknown:
prove prove the only way to exhaustively prove something's a prime number is to actually divide every possible number into it. Right? Mhmm. And you forever. It takes half it takes half the number. So in other words, if I had if I was trying to figure out if, like, 10 was a prime, the square root of 10 is three point something. Right? Mhmm. So in other words, I can go to zero I can test one, two, and three because two, you know, you'll get all the higher you would multiply it by a number bigger than that. Right. Right. Right. Yep. Right. And then you get to three, and you're like, okay. It's three times three. If I did this with 10, it's like like sorry. I get to two, and I'd say, oh, it's two times five. Right.
[01:00:17] Unknown:
You don't need to go beyond the the midpoint. I don't need to test five again. Yeah. Yep.
[01:00:24] Unknown:
Right. So I can test all the numbers up to three. If I have a 50 digit number, I there's, you know, whatever the square root of that is is 75 digit number. And it's gonna take more time than you have on this earth to test that to test every single one of them. This is why cryptography works. Okay? This is this is also the reason why it's, you know
[01:00:47] Unknown:
Alright. Let's read Boost. Okay. I got them up. You got them up? Alright. Yep. I got them up. We've got, anonymous with a thousand sats. Great episode. Really like you in this format. So So somebody that's seen either you or me in another format thousand. Appreciate it. Likes us in this format. And, Glimmerin, thousand sats, it's good stuff. Simple, succinct, and I totally agree.
[01:01:16] Unknown:
And, thanks. Guys. I mean, I really appreciate communication, and I know there's some of you guys who have been like, please stop killing me here. And I know this is getting hard on some people, and, You know, bear with us. We're getting better. I love feedback. I as I said, I signed up. I've never had somebody boosts on a podcast. I signed Higher Truth I signed Higher Truth to feedback with boosts. Yeah. I say that semi jokingly, but only semi jokingly. Yeah. Yeah. Yeah. But I appreciate all the feedback,
[01:01:48] Unknown:
but and especially the boost. Well, it's it for me, I was like, I pulled up fountain and I was like, okay. Let me just go look at, you know, whatever. And I click over to, like, the the wallet tab, and then I was like, oh, wow. Like, people have valued this thing, and it was a motivation. Like, it was it was this is the first time that I've I've actually had, like,
[01:02:10] Unknown:
some people are streaming. So we don't see that here. But some people are streaming sets.
[01:02:17] Unknown:
Oh. Even still, like, just that that that just magic the magic Internet money magically lands in in my wallet.
[01:02:24] Unknown:
It's nice. It's just astounding. And so thank you truly to everyone. I mean, if if the video thing gets off the ground, that'd be nice too. I'm I'm really committed to especially the people who have stuck who've just stuck with us here. Like, I'm really committed to paying paying you guys off with, you know, knowledge and insights. And I just I have a strong belief it will. Thanks for sticking with us.
[01:02:53] Unknown:
We're gonna get there one formula at a time.
Introduction and Elliptic Curves
Understanding Groups and Closure
Elliptic Curves and Cryptography
Fermat's Little Theorem
Euler's Theorem and Relatively Prime Numbers
Public Key Cryptography and Diffie-Hellman
Challenges and Insights in Cryptography
