Skip to content
PodSubs
ShowsPeopleGuestsJobsNewsEvents
More
BlogPodCred
Menu
ShowsPeopleGuestsJobsNewsEventsBlogPodCredNetworksSign in
Join nowSign in
  • Shows
  • People
  • Jobs
  • News
  • More
    • Guests
    • Events
    • Blog
    • PodCred
    • Networks
    Join nowSign in

Magic Internet Math

Magic Internet Math artwork

Elliptic Curve Cryptography: Inverses and Group Structure

Mar 2, 20261 hr 32 minAudio

The Study guide: https://ecc-study-guide.magicinternetmath.com/guide.pdf In this episode of the Magic Internet Math Podcast, the hosts continue their exploration of elliptic curve cryptography, focusing on the inverse problem and the mathematical structures that ensure its existence, as part of their series on Bitcoin security. Key Topics: Inverse Problem Modular Arithmetic Groups and Fields Euclidean Algorithm Fermat's Little Theorem LibSecP Library Summary: The hosts emphasize the importance of understanding the mathematical foundations of Bitcoin, specifically the inverse problem, where a public key can be inverted back into its corresponding private key. They highlight that the existence of an inverse is crucial for the security of Bitcoin, ensuring that transactions can be verified and private keys remain secure. This is supported by the mathematical structures of groups and fields, which guarantee the existence of an inverse for every element under certain operations.

Audio and video play straight from the show's own hosting. PodSubs stores and serves no media.

Transcript

From the show. Tap a time to play from there.

All right. Good morning. Good morning. Let's let everybody know what time it is because, you know, that's important here. But good morning, man. Have you said your good mornings? I just did. I just did. You got it on camera. You got it recorded. That's right. We do have it on camera. This is the Magic Internet Math Podcast, Episode 4. and I think this will probably be the second part two of what we called the elliptic curve cryptography study guide.

Yeah. We started in last week talking about some clock math, which formerly known as modular arithmetic. Very powerful. Probably one of the things I'm the most excited about that has ever existed in the world is this ability to do modular arithmetic just for the hell of it. Just because we can. Yeah. And then like, what has that given us? You know, not to think, boy, this thing out too much, but I just, it's such a primitive,

it's such a powerful primitive and it's going to fit. It's going to feature very heavily now and what we're going to talk about today. Yeah, I'd say so. I think what we did last time is we kind of at a very high level connected the core concepts of these math pieces that actually relate to Bitcoin. And we kind of at a very high level, like a survey level, just quick pass through, talked about all of these mathematical interdependencies that make the system of Bitcoin security, which is the public private key pair.

Right. And so we're going to slow it down a little bit today. We're going to go a little bit more into some of the interesting mathematical properties that yield that. and if I would recommend starting it last episode even if you don't grok 100% of every single beat you'll see kind of the big picture vision of what we're trying to connect and ground these concepts for which is the securing of bitcoin getting a public agree being able to have a private key being able to reveal information that you have a private key but no one else knows that private key

and the mathematical properties that we use with this a little bit of curve we're going to slow it down a little bit more today and talk about a lot of those like smaller building blocks. Yeah. And I like, I mean, high level is a great way to put it. And it's just that if you don't, if you don't like, you don't see the depth of it, what's the meme with the iceberg where all you see is the tip of the iceberg. So like at the tip of the iceberg, you see Bitcoin working, but like, I feel like in some ways we're the bearer of bad news by pointing out,

we're starting to talk about the bottom of the iceberg and just and say hey trust us for now that it's connected stick with us right and um i think it's important to see it even though we you know don't kill the messenger we are that's we're we're trying to create a rich conversation here for an understanding of something we all really care about very deeply yeah i would say last episode we sketched out the shape of the entire iceberg and now we're going to start coloring and all of the little details at the bottom and work our way up.

Yeah. Yeah, it's good. So I can't overemphasize. Oh, the thing I forgot to say was go look at the study guide in the show notes. That was like the one mental prompt I gave myself before I just said what I said. I forgot. Go look at the study guide because what we're doing now is I think we have a little bit of a three-way attack on this. We have this podcast where we awkwardly explain these things. But mainly I think what we're doing in the podcast is we're showing you what's important. And then when you want to go and really grok it, we have a study guide and I have a YouTube series now that is available in the show notes.

So like I think if you want to – I mean obviously I don't think anybody expects to master the math of anything by listening to a podcast, right? And I think my experience of doing this the first time with Gary, shout out, is it's hard. It's like frustrating. A lot of people said, man, it's so hard to sit through this podcast. So like what I want you guys, I think it's less difficult to know there are supporting, other supporting tools now.

Yeah, I would say every person learns differently and kind of what's effective for them to be able to unlock concepts. me personally what I would do is I would read the study guide then listen to the podcast because when you read the study guide and you're able to throw your hands up and say this is too complicated for me I don't get this when we go re-explain it on the show that may be able to provide you different mental models to be able to kind of get across the chasm and then additionally drop us a comment on fountain if there's a part that you want us to go deeper into

absolutely like if you're listening along you're flipping through the study guide you're listening to the podcast and there's things that you just still don't quite get like just drop a line to us and it could be like a little bit of an asynchronous uh study group that we all go through on this journey together oh yeah i should also mention before we jump in too quickly is that um i mean this is going off a lot of people but like there are there is a membership available at the magic internet math academy and um right now what

you see is everything that is there is freely available. So that's just the tip of the iceberg. So I haven't yet identified what's below it, but there will definitely be like subscriber only content. And there's a few people, it's like $2 a month. Um, if you want to do that, um, for a very limited time right now, I'm accepting lifetime memberships, um, in Bitcoin only. And so we have four members so far, shout out to those guys. And, um, so let's get to it. Make sense?

That sounds good to me. All right. So I think what we want to do is start with Chapter 2 of the study guide. Okay? And so anybody who already looked at study guide is about to pay off by knowing what's in Chapter 2. And we did – you know, we hit this last week, but did – I mean, this repetition is everything. And so we're going to repeat – what Chapter 2 is called is the inverse problem. And, you know, inverse is, it's like of real importance to know that your private key, which is a point on the elliptic curve, right, gets multiplied by some generator that is another point on the elliptic curve that the public sees.

It's of utmost importance that you know you can invert that public key back into your private key. Right? Like that is of, imagine if for some reason you were in a number system where that was not possible and it can only happen by dividing by zero, which anybody who's ever tried to code anything knows how easy that can happen at a given point in time if they're not severely restricted by the number system they're working with.

So what we kind of talked about with modular arithmetic a little bit and then gotten to groups right we went we went very we took a very large leap across stones and went to groups because what groups and fields do is ensure and what they really do is ensure the existence of an inverse that's one of the things they do and when we're dealing with things like hash functions where you know you just have to knowing the math allows you to know the inverse exists without really

being able to do the math with a pen and paper or even with a computer. Right. So like we're kind of in this realm of like, you have to, you have to, there's certain things now you do have to trust and you have to trust an inverse exists with a hash function, even though you can't really do it. Like, you know, you know, if you're into real numbers and you have a number five, you know, one fifth is the inverse of that. You can handle that and your brain can handle that. If you're in a certain number system

That's, you know Most number systems and most numbers Your computer can handle, right? But the whole point of this The whole point is your computer can't handle it And no computer can No group of computers can In fact, as long as you're on this earth And subject to the constraints of energy And the current state of, you know Algorithms and all that there's nothing you can do to actually sit and prove that your inverse exists. You have to trust the math on this one, but that's why we're here. That's what I'm motivating at the moment is,

how do you know you have an inverse? And this is, again, as just one high-level concept we talked about on the last podcast, is that the reason why you basically have to remove a brute force like always checking and you have to go to an abstract theoretical proof is that the number of points on this curve outnumbers the atoms that exist in the universe and since it requires energy computation and time none of this stuff is free even with moore's law

and like doubling every 18 months the ability for us to compute things this is so many orders of magnitude outside of the scope of what could be kind of infinite like being able to definitively every single point on the curve proving it has an inverse through brute force is impossible you're you're looking at the heat death of the universe even with quantum times over which i mean i feel like we'll mention the word but like even it's true but so like the thing that's a good point with quantum is that quantum is not going to be able to definitively show every single point on a

curve, it can find an individual point of a public key and find that one inverse to the private key. But it's not going to be able, theoretically, but it's not going to be able to brute force and show the universe of all possible keys. Yeah. So what I kind of want to, before we get into it, it's like when you go to the Bitcoin store and say, I am ready to buy Bitcoin, right? Theoretically, as a customer, you already, I don't know how many people own Bitcoin, But every single one of them should have gone to the counter and asked to see the manager and say, I need you to – before I buy this Bitcoin, can you just show me that I have – that an inverse exists to my private key?

Theoretically, that is the thing you should be doing at the store. Yeah. OK. And that's called verify. OK. That's the thing that we call verify. When we say don't trust verify, I think in my opinion, it goes that – it should go that deep. Like how do you – Well, it has to because otherwise, how do you know if you generate a Bitcoin address that there's actually a corresponding private key? That's right. Until you check it yourself manually. That's right. You can't. So this evergreen idea of an inverse is the way this happens.

Right. It's the way a person motivated to actually maybe who has that a good natural barrier for not wanting to trust his life savings to a bunch of zeros and ones that may or that may not pan out or be spendable. Right. This is a big this concept of inverse is now that is one of the things that can get you over a very big hump. I'm really saying you should be asking this question. People should be asking this question.

People should not tolerate owning Bitcoin and not asking this question. So what I would love to do is we should explain this inverse property. And then I'm going to tie it into LibSecP and how the library actually works. Because it's a little interesting thing we'll get to. But I want to lay out the core math first. So, okay. So real quick, before we talk about an inverse, we're going to talk about something called the identity. So this is very abstract. However, there's a reason method for it. So like, you know, an identity under addition, I think people can handle is the number zero, like that's the identity, meaning like zero plus anything is that number. Right? So like, when you talk about an identity, you want to know that you it's the thing. This sounds so like pedantic, but it's really, really important.

it's like what can i how do i operate on a number and not change it at all and the answer is you use the identity you you operate on the identity and that's really important and the identity changes based on what the problem set is so and the operation and the operation so i think the other one i think most people would be able to think through is with instead of addition multiplication And I want everyone to take a half second and think before we say the answer. What do you do in multiplication to get the same number after you multiply it?

That's right. The number one, right? Two times one is one, right? So you can see that the identity is not a constant across all methods and all perspectives. But the identity as a concept, though, existing is really important for the stuff we're going to be talking about. Yes. And this is why we talk about groups, rings, and fields. Because a group gives you an identity for an operation. It doesn't tell you what the operation is, so it doesn't tell you what the identity is.

However, a group is just a primitive to understand this concept that you have, again, closure, identity. And if you have identity, you have an inverse. because the inverse is the element that gets you back to the identity. So when we talked about addition, in the integers, let's just say, if you have the number 5 and the identity is 0, because we said 0 is the identity for addition, then the number that gets you back to 0 is negative 5,

which happens not to exist. Well, no, sorry, it does exist in the integers. It does. Yes. So under addition, you're good there, right? So five plus negative five is zero. So therefore, negative five is your inverse, your additive inverse, your inverse under the operation of addition. And to take it to multiplication, if I have the number two, what can be combined with two to always get back to the inverse? Well, what is the inverse in that case that gets you back to the identity of one?

It's one half, right? One over two. So two times one over two equals one, which is the identity. So that's another example about how you can get the identity and you can compute it depending on the field, like what you're doing as the operation and changes. But there is an inverse that exists for all the real numbers, and it's one over that. And we're so confident in our – the human race is so confident about this. We've given both of those things names because they're so general. We call the additive inverse like an opposite or a negative, a negation.

And we call the multiplicative inverse a reciprocal. And I'm saying this because I'm pretty sure everybody knows what these words are, right? But now I want those words to be associated. It's easier to associate this concept now. Yes. The reciprocal is the multiplicative inverse, and the negative is the additive inverse. And why do we focus on addition and multiplication here? And why do we talk about rings and fields? It's because in a ring and a field now, you have both operations, addition and multiplication.

and so um in a field a field is like a perfect version of a ring where you have an inverse for both right you have an additive inverse so i don't want to get to a field here but like i just want the reason we talk about fields is a field is like um a statue and the ring is more like the block of clay that we know can become a statue yeah right and this and the reason why we're doing this is because remember what we talked about on the last episode is that we're not dealing with

just the number line and all the real numbers there's a very particular set in order of the points that we deal with in the bitcoin elliptic curve which was y cubed equals x squared plus seven that's where this all works and we're not looking at everything we're looking at things within that subset and the relationship of how that all works, which we briefly touched upon last episode, creates a field. And that's where the modulo arithmetic and everything starts coming into play, is that we're not just doing negative infinity to positive infinity.

There's a very particular set of numbers that we're working on. That's right. I mean, imagine being Satoshi, right, and worrying about, worrying in 100 years that Someone's going to try to spend, you know, do a spend and they're going to run into some divide by zero or infinity thing. I mean, it's like it had to be eliminated. Right. It had to be eliminated on day zero. So we have we use a number system, not the integers or the reals.

We use a number system called a finite field modulo prime. And I know that's confusing a little bit, but if you go back to last episode, we talked a good amount about it. And it's really just a compact system that operates under the operations of addition and multiplication. And if we go back to the modulo arithmetic, it just so happens that modulo arithmetic follows the same rules as regular arithmetic almost across the board.

And so it's a very nice, convenient way of now being able to do math, this type of math, in a way that ensures this structure. The structure, again, meaning closure, identity inverse under addition and multiplication. This is just – and the reason – and here's the thing I can't reiterate enough. Why do we even talk about this structure? It's like – I know everyone is like, why the hell are you talking about this structure? It's so alienating and I'm already confused. And the answer to this is that you can't do this math on a pen and paper or with a computer or with all the computers in the world.

So you have to be able to trust that the math is doable no matter what and no matter what the situation is. Yeah, and I'd even add we're just laying out the axiomatic baseline principles of where you get to the point to be able to understand the system works as it is designed. And it's less axiomatic. Like each one of these has a mathematical proof and a reasoning behind it. It is not – it is because we say so, which is what an axiom is, right?

It's like just a definitive like base truth. But we're trying to lay out all of these theoretical concepts so that you're able to know, not trust how this all actually works. That's right. It's all about knowing without even – without the ability to actually do it. Normally the way I know how arithmetic works is I sit and do it. Right. I know three plus three equals six. I can sit there. I can count my fingers. I can, you know, I can know that. The things we're talking about are in a world where you just can't know by the same type of ways that we know things.

and it's not even like we can even trust our computers to do it either. You have to know that the structure, you just have to understand the structure and say, you know what, the structure preserves these important things. It discards everything else, right? I don't need to know anything other than that these operations of multiplication and addition are preserved and that these properties of the group are preserved. That's all I need to know to be able to essentially have knowledge of this kind of unverifiable thing.

Right. So with all of that context laid out, let's talk about these multiplicative inverses and how they work with Bitcoin. Yeah. Before we talk about Bitcoin, let's just really in a finite field. you know like i'll talk about a finite field maybe modulo seven and one like modulo six right like so like that's a good place to start just keep it super simple base abstraction of the concept in uh a domain space which is very easy to understand

that's right so like and once again i should have all of this written out and prepared out prepared out so i'm not doing this in my head however let's just look at a finite field modulo 7, which we said would consist of the numbers 0 through 6. And the reason why is if you got to the number 7, 7 divided by 7 is 1. Actually, it doesn't include 0 either, so my bad on that. There you go. But 1, you know, 1, 2, it's basically what it does.

Remainder, sorry. The remainder is 0. If you do 7, the remainder is 0, so modulo is 0. That's right. Now, I do have a video on this that's buried in my YouTube site that I did last year. But basically, what you have, the finite field consists of all of the numbers that are relatively prime to your modulus. So any number relatively prime to 7, which if that number is prime, it's all of the numbers before 7. So 1, 2, 3, 4, 5, and 6 are what you call relatively prime because they don't share a common factor. Whereas if the modulus was 6, then you don't have that finite field because 2 is – you have 2, 4 and 4, which are not relatively prime.

So these numbers don't have inverses in the modulus 6 because I would say 2 times 3 is 0. So that's unacceptable in a finite field. So now you have no inverse. What you're looking for is two numbers that multiply to one. They're called associates. But that's what you're really looking for is that you have a number in your number system. And you have two numbers in your number system that can multiply to one. And just to drive that home, why you don't want to be able to get to zero is that if you get to zero and multiple points get to zero, you don't know what your original input is anymore.

You can't get there. That's right. You cannot guarantee now that the random number you created can be traced back Right You have a collision in another way You have two different you could have multiple numbers that result to the same point on the curve which doesn't work. Oh, you know what I'm being reminded? So I'm creating a basic algebra series, like high school algebra series. And one of the, I think when we get into inverses, there's this story in mythology

about somebody who had to go through a cave and fight all these monsters. And the gods gave different weapons to different people. And the person who traversed the cave is the one the gods gave a thread. Because everyone who went in this cave couldn't find their way out, except the person whose weapon was a thread was able to find his way back out of the cave after being able to defeat all the monsters in the cave. And that's like really what this is.

This is you holding a thread in a dark cave and accomplishing whatever the quest is and finding your way back out of the cave. And you want to – but you have to – the thread is the thing that tells you you can find your way out. You're not going to be lost at sea, right? Totally. And I think in the interest of building that thread, let's keep it to the simplest example with Modulo 7. let's say okay 1 modulo 7 is 1

that's my identity 2 modulo 7 is 2 and you can go all the way up to 6 is you know 6 right and like if you jump ahead and say okay what's 10 modulo 7 well if you divide 10 by 7 your remainder is 3 so your remainder is now 3 so let's talk you want to hit the you want let's identify the pair the associates that you know

when you pair them up are inverses of each other in the in the finite field modulo seven so if we have two right the inverse is the thing that we multiply to two that gives us one which is four because 2 times 4 is 8, modulo 7 is 1. So 2 and 4 are called associates and they're basically 2 is the inverse of 4, 4 is the inverse of 2. Just like in the reals, 5 is the inverse of 1 fifth,

1 fifth is the inverse of 5. But in this number system, the finite field modulo 7, 2 is the inverse of 4, 4 is the inverse of 2. If we hit the number 3 Right And I think the inverse of 3 is 5 Because 3 times 5 is 15 Which when divided by 7 Has a remainder of 1 So 2 and 4 are associates Inverses of each other

3 and 5 are associates So what have we left? 4 and 6 Sorry We have we have two and we said two and four three and five yes so we're three five and so six is kind of six is special you know why because you start going through well that's the only number left what the heck right well six before i do before i do the big reveal six modulo seven is six but

it's also negative one as as it happens and this is a very interesting property because the number less than 1, it's its own inverse. Because negative 1 times negative 1 is 1. 6 times 6 is 36, which, you know, modulo 7, 7 times 5 is 35. So 36 minus 35, remainder 1. So 6 is its own inverse, and the prime, whatever the last number, like the largest number in your finite field,

is always negative one and it's always its own inverse kind of cool yeah right it's like the and then that's the last that's the last one so we identified so it's it closes the field everyone has a buddy that's right everyone has a buddy and one obviously has a buddy we forgot we forgot we never want to forget one that's true it's very easy to do so everybody has a buddy and your buddy is your thread out of the cave right and it's like the way

so that when you go to the bitcoin store you don't have to tell people hey can you make sure you prove to me that my guy has an inverse so that my point is back on the curve you have to trust that no matter what operations you do you will always be identifiable on that curve it's cool these inverses Like you're saying, when you're going to the Bitcoin store, it's basically when you're verifying a signature, you're doing this. This is what you're doing.

Yes, you're verifying that the point exists. And when you're going to the Bitcoin store saying, hey, I have one Bitcoin, I want to spend it somewhere. The whole network is doing this math of finding the inverse to prove that you own the private key. That's right. Pretty sick. Now, are they really doing the inverse, though? That's the question, right? Because it's like they're not right. They're not really doing the inverse. Correct.

Does that take us to the next point? Maybe we'll just put a pin in that one, right? Because a couple of primitives I think are really like, so I think that I do want to talk about the Euclidean algorithm. That's what I was trying to tee up next. Yeah, let's go there. So like none of this Euclidean algorithm is A fancy name for something We all started doing when we were Seven years old which is long division Right or I'd say when we did Long division when we were seven

We were kind of We were doing the Euclidean algorithm without Without the name Would you say? Yeah you bring it to a level When you get to the point of long division Like third fourth grade you've done your addition you've done multiplication you started doing some multiplication and now what you're doing with long division is you're combining addition and multiplication to kind of undo the whole thing yes and we did this in a field we didn't know it was a field we didn't know that all this stuff was nice

but we did it in a field called real numbers right and with well using integers really just using we using integers as coefficients maybe we could say we did it in a ring a ring of integers but we didn't know about the structure we didn't know why this would all work frankly not to get to a field again but we don't we don't realize that a number is actually a linear combination it's a polynomial a number is a polynomial which in polynomials form rings and

And this is actually why a lot of this works as well, meaning like the number of 5,262 is 2 plus 6 times 10 plus – I already forgot the number, but you get it. It's a linear combination of powers of 10. And we have powers of 2 in our binary numbers that are just – these are polynomials. They are a ring. we do the Euclidean algorithm on a on a we're pulling apart that polynomial with the base

would it be fair to say Euclidean algorithm like uh it's basically maybe another term from like fourth fifth grade math like greatest common denominator it's a way of finding that it's a way of finding that and usually when we were in third fourth grade it was heartbreaking to have to find a remainder we're like oh no no I hate why isn't it nice and easy even and it all goes in nicely yeah right but it's basically finding whether or finding a greatest and in in our parlance we call it greatest common divisor so when i mentioned

relatively prime before basically when two numbers are relatively prime it means there's no more there's no more division you can do with any of them you're sort of at the bottom of the barrel of how much you can reduce your system but when there are greatest common divisors this can This comes up a lot like something simple like in the Pythagorean theorem, right, of trying to sort of solve a lot of that stuff that, you know, you have a 3, 4, 5 triangle, 3 squared plus 4 squared equals 5 squared.

But like that scales. Like, you know, that can all scale with size. So 3, 4, 5 and a 6, 8, 10 are kind of the same thing. And so we only want to really, in our systems when we do this, we only want to operate in the system where there are no common divisors, right? That's just sort of like a, it's not an axiom. It's more of just like it makes it faster and easier to just always be, to not be that redundant, right?

To say, well, it's kind of similar to modular arithmetic. It's just we're operating in the lowest kind of lowest atomic element of being able to divide these numbers. So what the Euclidean algorithm does is it uses this recursive – that's what the algorithm kind of means. It uses this recursive division of finding remainders to ultimately get sort of to the end and find out if there's a greatest common divisor between two numbers.

Well, find out what it is. And if it's one, that means those two numbers are relatively prime. So that's all to say Backtrack a little bit I get a couple numbers like 6 and 7 I know they're relatively prime I know that if I divide 7 into 6 I get a remainder of 1 Boom That's how I Their greatest common divisor is I know they have no common divisors But if I'm dealing with numbers that are hundreds of digits long It would be really nice

If there was a way to find out If there were greatest if there was common divisibility, numbers of common divisibility among them. I'm happy you started with six and seven for the 12-year-olds that are in the audience. You did it. Oh, they should stop the podcast right now. Yeah, it's all over. No, but this is a really important point though, right? Is that being able to quickly be able to derive and understand these properties is just very important for doing this at scale. and so while the greatest so the euclidean algorithm is a powerful way that this is

this is a rich thing in and of itself because um a it's a powerful way of finding common divisors which is actually really important with that with a common in order to know that your field is real is fine you have like a finite field, you have to know that any two numbers are relatively prime. That gives you the property of the, that's part of what gives you the property of the inverse. So like the, you already know there's a fly in the ointment. If there's a greatest common divisor of any two elements in

your finite field that are not one. So that's like an important thing to be, that's one way to verify, it's one way to verify this, right? It's also that you can, um, there's this um i was telling you before we started like when i was learning all this a couple like a year ago or two and i was like really looking to try to teach it and grok it you know one of the things i like i like in a textbook is if there's like a code implementation that really

shows me and this is like part of how we got here to begin with because like bitcoin's code implementation is beautiful it's like so informative libsec p not so much right and um it's like what the hell right so if you ever ask like i asked chat gpt that was like the best ai at the time i said you know make me a function for the euclidean algorithm um i encourage you guys to do that because and it's what's so interesting about it is it'll give you literally one of the shortest, it'll give you a one line formula. This is what I got one line that is like

actually not maybe 30 characters long. And I didn't find that very helpful. Right. I was like, what, what, what is going on? And then it's like, I wonder if you need to go to school for computer science to understand this right but the more that's ironic that the more i repeated the more you repeat going through this and the more i did pen and pencil exercises on the euclidean algorithm just like any two numbers you just do your pen and pencil exercises and i don't know how many it

takes but at some point it clicks that it's this recursiveness is uh it's that it's because it's recursive is very clever that you could do it all in one line and just say, just, you know, go until essentially go until, you know, until you can't go anymore. But, um, and then output either one or whatever the final number is. Right. And if like, it's a lot of what we do here

is about going in, it's inside out. The way you learn is inside out, not outside in, You go to the bottom of the iceberg and you start climbing your way out. And so I would encourage people to do exercises on the Euclidean algorithm and inside out with real numbers. Because this is, again, it's the way, it's the beginning of understanding why, A, trusting.

I mean, trust is a bad word. It's the best word I have right now for saying, how do you know it actually works on numbers you can't do this on? You can't do it by hand or on a computer. So I don't know if you had any more on that one. Rob is deeply thinking. this is deeply thinking and a microphone on mute when i'm talking uh so looking through this like

i think the pen and paper exercise is good if people want to kind of follow along and i think the study guide is like a great way to like tee up the context around it um do we want to tie it back to finding the inverse with the extended euclidean algorithm yes yeah we should do that I call it There's a lot of things you can call There's a thing called Bayes-Out's identity Which So basically when you do the

It's like when you do a long division You can then put that process in reverse To find The actual You can come back to the two numbers You were trying to Reduce to begin with Right How would you approach this explaining this in words well this is just the idea that um you since the nature of multiplication like we're talking greatest common divisor like divisor denominator whatever like you're taking

a system you it can go both ways so you can start with the numbers that you're looking to find the greatest common divisor or you can start with what that number is and work backwards to find the original numbers again you're basically taking both sides uh you can go a to b or b to a and Those are the same idea. But I guess the powerful thing you have with Bayes-Out's identity is that what you have – if you do have two numbers that resolve sort of – that are relatively prime, that the algorithm tells you are relatively prime, right?

Then what you now have is a linear combination of those two original numbers that resolve to the identity. and so that you can sort of see the, you know, it gives you now powerful algebraic ability to eliminate, you know, to eliminate like a lot of factors when you're now doing math with those numbers, which is really what you're doing to begin with. I know that probably didn't connect, but it's just like what Bayes-Out's identity says

is that two numbers that are relatively prime, you can have any linear combination of those two numbers and it'll equal one modulo that prime. So in the modulo arithmetic world, that's, you know, so anytime you have numbers, anytime you have anything, when you operate it and it resolves to one, i.e. your identity, you're going to be able to use that to essentially make the math easier down the line.

um i don't know if that really covers i don't know if that really covers it i'm i'm pulling up right now to do a but that leads to format's little theorem which i think is like one of the most important things anybody yeah yeah and i think like no in the bigger picture we're talking about this large finite field for all the bitcoin stuff but like let's just talk about it at the simplest level if you were to take very small numbers right so let's let's start with um

i have here i just please don't choose six and seven please don't choose six and seven let's do uh the inverse of three modulo 17 so what you're trying to do is you're trying to say three times what equals one mod 17 right so you have this number 17 and what you do is you could take well that's three times five plus two it's because three times five is 15 plus two is 17 right yeah 17 is divided by three uh 17 divided by three is five with the remainder of two

and so you have three now equals two times one plus one and then you hit a remainder of one you stop you found the answer now phase two is to build it back up you're kind of walking backwards wait hold on hold on hold on yeah hold on um your remainder of two basically means that it's not your inverse though you what will you really keep on going you have to keep on going until the recursive nature yes that's right so you start with 17 right and you're trying to say again the question is is so you do a euclidean algorithm between you do you try use the euclidean

algorithm to try to find the greatest common divisor of three and 17 and this is like the tool this is very hard to talk through right but this is the tool of help helping you find the inverse of three with respect to 17 in that finite field bingo and so just to walk through it again the question is if you're taking the inverse of well so you're saying in the problem is what number do i multiply by three in modulo 17 do i get one and so you say okay well i have this 17 number

equals. And what you do immediately is you start factoring out, you get three times five. Well, I get, well, no, because I get a remainder of two. I get a remainder of negative two actually with three times five, which is five. Well, it's the first step. So I get a remainder of 15, I get a remainder of 15, right? Negative two is negative two is 15 in this system. Right. So I get, yes, there you go. Right. So you have to keep on going. Right. So that's the first step. So if you're doing this with pen and paper, you have to keep on going. Right. And, um, You can then go one more lap and say, well, 3 divided by 2 is 1 with a remainder of 1.

And you hit a remainder of 1, so then you stop. So what does that tell you, though? Let's just zoom out for a second. In the modulo 17, I just know the answer is 6. I know 3 times 6 is 18, which gives me a remainder of 1. So the real question is how does the – I don't know if this can be talked through or if it's possible without a pen and paper. But like how does the Euclidean algorithm in general get you to that inverse? And it's – I think what it comes down to is when you're doing it, you realize that one of the things you're – the base thing you're multiplying by is essentially going to be – you can zero it out because it has – you can zero it out because it has – it's a multiple of your modulus.

Right. Right. It's like, and then what's left, when you finally get to a number that's lower than 17, that's going to be your inverse. And maybe I do need to code up an example here. Three times six equals 17 plus one. There's your remainder one. That's right. So I know the answer is six. It's very hard to take people through the steps of this thing to see that. we're gonna have to upgrade the production value and get a nice little interactive whiteboard going

here yeah i'm on i'm like i'm i'm on it i'm thinking about it that's why like the youtube series is was designed to support this so you can see examples and you know when i it's like when we sort of step in shit like this that's when i discover what what's needed yeah the way i would view it is like if you're viewing like this this field in this system is like a machine what you're doing is you're labeling each part and disassembling it and reassembling it like ikea furniture like like that you know that's what like it's ikea furniture a field is like ikea furniture every

single piece has a piece that you click in and there's instructions on how they all interact with each other and what we're doing in these operations is we're provably showing that you can take it apart put it back together and kind of complete the system yes and i think i think i'm Debating whether to do this right now But I'm going to do it I want to read I want to read the What I call the Steiner's lens Blurb from the You know From the manual From the study guide Because I just think it explains It finally does put words

And explains like What I think is important here So I'm going to do it Okay So basically Steiner Distinguishes between A finished thought Which is like a proposition We contemplate from the outside and a thinking activity which is a process we follow through transformations So the thinking activity is like the algorithm. So an algorithm is closer to the latter. It is a living thinking, not a static truth. When you follow the Euclidean algorithm, you're not contemplating a fixed fact.

You're participating in a thinking process that unfolds in time. Each step transforms the problem into a simpler version of itself. So in the example here, the greatest common divisor of 252 and 105 can be reduced to the greatest common divisor of 105 and 42. I'll just pause for a second to say because you can you can get through that

that should be a step that people can do self-evidently but by doing the division 105 goes into 252 twice with a remainder of 42 so they have this you have the same greatest common divisor between 252 and 105 as 105 and 42 and then you do that step again and you get a GCD of 42 and 21, which maybe some people recognize as 21 because 21 times 2 is 42. So basically, again, you understand the algorithm not by looking at it from the outside, but by doing it,

entering into the process and following it through each transformation until it reaches its conclusion. That's what I wanted to read from that. And what I want to kind of like also mention is that I just, I've always thought about this thing with Rudolf Steiner. My kids are in Waldorf schools. And one of the things I noticed very early on with my kids in that school, as it applies to this, is every kid in Waldorf school, an adult, if you ever go there,

is knitting. Knitting is a big part of the education. And part of it, what they talk about is emphasizing working with your hands. But what I saw was, particularly with crochet, is that you trust a pattern and then you do it. And you don't know until you're done that it was going to work. But these people who look like hippies that sit around knitting all the time, they actually have high conviction in this algorithm.

Right. And I remember seeing that for myself and telling people, you realize you guys are teaching math here without realizing it because this is like you're teaching people to trust an algorithm that's going to lead to this. And, you know, there's a reason why it always works. And, you know, if you if your pattern didn't didn't come out the way it was supposed to do, you messed a step up in that process. But you learn by doing it. You learn by putting yourself through it.

Just because we have computers and AI doesn't mean you can shortcut that process of learning. And so I would think of it like knitting a sweater. All you know is the next step and the next step and the next step and the next step. You're just repeating the same thing. But you do understand the structure of the thing and why it's going to – you do sort of understand why it does turn out. Because why would you spend your time playing around with needles and threads like that if you didn't know it was going to turn out cool in the way you thought it was?

And so it's like it's internally like you it's it's like internally to you as a human being. You get to gain the experience of, you know, this algorithm, which traces back to YouTube. Like no one's improved on this in 2000 plus years. Right. it's pretty remarkable and at the base of it again it's just really trying at the base of it we're trying to find out if two numbers have a share a common divisor yeah but it gets you but

it also helps it's so powerful that it also you know this traces back to the inverse problem and i often think too that like sometimes like the reason why something like this like is thousands of years ago and we haven't really been able to iteratively prove on it is because it's just it's so simple and back then you did not have the aid of technology to try and like accelerate and complicate things and get more abstract you had to just sit there and think about it that was really your yep that was really what you had and it's a beautiful property um it's how i got to

grow up too like in life i feel like kids without the internet got to grow up really sitting and thinking about the things they're doing like that and all the more reason why i think it's good to emphasize um spending this kind of time if you know again you it's this is all how the substitute for being able to go to the bitcoin store and ask to prove to you that your key exists yeah and should yeah should we take this now too because we keep there's a reason why we mentioned this a little

bit earlier we're doing modulo 7 modulo 17 like we're very bold you were very bold and going for 17 yeah well like the idea though the idea of why we're picking these numbers and we mentioned it briefly earlier is that these are the what's unique about these numbers are they are prime numbers right do we want to take this maybe a little bit to fermat's little theorem yes we're gonna go to fermat's little theorem which um everyone knows about fermat's last

theorem but frankly fermat's last theorem isn't that useful to us fermat's little theorem oh my god one of the most powerful incredible um little factoids that this is what we we're now possibly we're taking the pin out of are you really calculating the inverse it's like what are you actually doing? Like that's, we're kind of uncorking that now to revisit that point from earlier. So you remember when we said, boy, anything that resolves to the identity is very

powerful because we can then eliminate a lot of the math once we, cause you know, you multiply by one over and over again, guess what? Nothing changes, right? So, um, it's nice to just multiply things by one i wish i could do it all the time but um you know take a number like um so but let's take this field modulo seven right and let's just take an element of our field that we know is a generator i think let's just do you want to just prove that two do we know if two is a generator

should we just go through that let's just go through the exercise go through the here so we get two and two times two is four right two times and then so we get two four and six well i'm this is on the additive side on the multiplicative side we have two four eight which is one right so two is not a generator because it only gives you two four and one it stops there so let's we got and you have a closed loop and it's not all of the points so that's not correct and for the

benefit of the audience once i get to once you get to one you're just starting the cycle again so two one times two again is two two times two again is four four times two again is you're kind of on rails you really can't get outside that that cycle yes so okay two is not a generator and there's a this is this is in a number theory concept called the primitive root primitive root it's not that easy it's not easy to find so that's why we define the generator in bitcoin by the way when you go to the GitHub, you see the big capital G

is defined already. It's the smallest number that can be the generator. Let's now try 3. I have a good feeling about it. Me too. 3 times 3 is 9, which is 2. 3 goes to 2, which goes to 6. 2 times 3 is 6. We get 3 to 2 to 6. Then we go to 18, which is in modulo 7, which is 4. 3 to 2 to 6 is 4. four times oh no yeah so then we go to five yeah four goes to 12 right did we do this right

are you sure we did this right three to six three times we're doing generator three yes three to six yeah so we go three six four to five wait sorry so three times three is nine three goes to seven is two three to two times three is six modulo seven is just six yes so i I just want to keep saying it. We go 3 to 2 to 6, right? And you should be in your mind's eye, have the numbers 1, 2, 3, 4, 5, and 6 and crossing them off as we identify this.

So we started with 3. We went to 2 and then to 6. So those are crossed off. And then 6 times 3 is 18. Which is 4. Modulo 7 is 4. Yeah, so it's 3 to 2 to 6 to 4. 4 times 3 is 12 that's modulo 6 is 5 so 3 to 2 to 6 to 4 to 5 and then 5 times 3 is 15 modulo 7 is 1 so boom so 3 is the generator 3 definitely gives us all 6 elements

you can create all 6 elements and remember this is the same thing we talk about when we say that the your points in the elliptic curve can all be generated by the big generator point, which means when you have a private key, any other number in the field multiplies to a point. That's all we just did there with prime being seven, right? Okay. So back to the... So if you have a... I don't know if it was necessary for us to just do that, but...

It's a good little refresh. It was fun. Because we talked about generators last episode. It's a good way just to kind of like nudge the concept real quick and we can go on to fermat so okay so in fermat we basically say any number any number in that field to the power of p minus one is one and so that's really that's really interesting you can go through the math on that but like we can just basically say okay we can actually say two to the sixth power is one when we we really did show it because we went to remember

we went 2, 4, 8. We just do it twice. 2, 4, 8, 2, 4, 8. That's 1, right? 2, 4, 1, 2, 4, 1. So 2 to the 6th power is 1. We showed the 3 being a generator. Clearly, 3 to the 6th power is 1, right? And then it gets kind of easy because if 2 to the 6th is 1, then 4 to the 6th is 1 also. Why? Well, because four is two squared and so bingo you know factor it you can just do the math and you're multiplying

one by itself now a bunch this is an important point is that when you find that point you can take that base number and multiply it again but you're just if you factor it out you're just doing one times one times one however many times you're putting it together and this gets to the power Because if 2 to the 6th is 1 Then 2 to the 600th is 1 2 to the 6 billionth is 1 Because, okay, let's just go back 2 to the 600 is 2 to the 6 To the power of 100 2 to the 6 is 1

1 to the power of 100 is 1 1 to the power of a billion is 1 You want to hear something kind of funny? I'm going to expose Part of my trick of how I taught my children A lot of this math Especially when it comes to algebra I get so frustrated with them not understanding these certain generalities that I basically showed them that I could substitute. I don't need the number two. I could use a toilet seat as a variable. And I should draw a toilet seat and put it to, say, the sixth power.

It's going to be one. Any number, you know, if it's in my finite field. And so, like, I call it toilet seat math where, like, it just doesn't matter anymore. Two to the sixth is one. And one to any power, one to the toilet seat, doesn't matter what it is, is going to be one. So here's the thing. So two to the 600 now we said is one. Two to the six billion is one. Two to the six gajillion is going to be one. Which really, you're starting to get to the point where, okay, remember what we were saying?

Like, I can't even do this on a computer. I can't even do this math. But I know because of Fermat's little theorem that I can actually eliminate a large portion of this calculation. I could reduce it to 1 and discard it. Right. So you want to know what would be – if I asked you 2 to the 1,000th power, right? You would basically look at the 1,000 – you would say, well, what part of this can be reduced to 1? right so i know that like i know 960 is gonna be one so i got 40 left right so 36 out of that 40

is gonna be one so i know that 996 i know two to the 996 is one which so if i wanted two to the 1000th it's one times two to the fourth i know this is horrible to talk well this is well well what you're doing here which is just important is that you're taking your bit you're doing factoring which we haven't talked a lot on this podcast but anyone with you know i would say in elementary school math understands the concept of being able to break a number into smaller numbers um and like the number 100 you could also make 10 times 10 and what you're doing here in this

exercise is you're breaking out each you're doing factoring but you're you're explicitly factoring out what can i factor out that goes to one because it's kind of just noise you're basically trying to you're removing everything that doesn't factor to one and then sitting in what's left. Which is in its own way, kind of what we've been doing with the modular arithmetic. Like, like what is a hundred module of seven? It's like, okay, well, I know 10 times seven is 70,

right? And so you just start pulling these things out until you get what's left. And then you, instead of doing math on the entire number, you basically take out the garbage for what you can. that you know just goes to the identity property immediately and then stick with what's left to do the remaining math. So Fermat's little theorem powerfully exploits modular arithmetic to make a lot of this actually really easy. So it makes finding inverses formulaic. As long as it's prime. As long as the field is prime. As long as the field is prime. Which should light you up as like,

oh, this is part of why my modulus in Bitcoin's elliptic curve is also a prime number. Correct? Yep. So that, you know, we're building, I feel like we're building a tower, right? So, you know, maybe the little parts of these bricks that we lay are a little painful, but we're building a tower to how do we know based on what we can see and visibly verify, right?

How do we know Bitcoin works, right? We're building a big tower. For Matt's Little Theorem, I have to say, man, it's one of the big mind-blowing things. And I remember in Jimmy Song's Programming Bitcoin book, like seeing it being used but not like really explained. And I was like, oh, my God, how do they do this? You know, and it's like, okay, no, I got to – you go into some number theory textbooks and you just see it. It's like, oh, my God. This is one of the real beautiful, beautiful things.

Yeah. I got some documents that – there's like many different ways to prove it. This is one of those things that people have walked into over the years because Fermat didn't like proving his stuff. But this one was easy. Maybe for the sake of the conversation today, we can explain what the exact equation is. And as a take-home exercise or maybe on a future episode, we can go into an actual proof of it. But if you have a field that is prime, let's call it P. Finite field. A finite field. If you have a finite field that's prime, let's just call that P for prime.

the inverse of a number is that number to the p minus two modulo p yes and so let's take our example earlier um of a finite field of seven and you want to find the inverse of three well uh what you can wait can i just stop you for a second because i feel like i and i i'm just speaking from my own experience sure like where did p minus two just i thought you just said it

was p minus one and you did this whole exercise to show it was that p minus one had this property why are we talking about p minus two so because without the benefit without the benefit of showing it on paper right yeah so the actual i i skipped a step of the actual theorem and i kind of rearrange things so to go one level higher um a so if a field is prime p a to the p minus one power equals one modulo p we just did that whole math we two to the six thousand we said two to the

six is one three to the six is one any number inside that field modulo seven any number to the power of six is one. That's the first thing. That's the first step, right? Because now what we're trying to do is, okay, what are the two? Now, if I take a number in that field, right? Yes, I can raise it to the power of P minus one, but that's not what really we're trying to do now to find an inverse. We're going to use that property. We're going to leverage that property to find the inverse, right? We're going to say, what number do I multiply it by

to get one. Right. And so to take it to the next level of the abstraction of the equation, if you're trying to look for the inverse of A in a prime field of P, the inverse of A equals A to the P minus two modulo P. And that's just basically rearranging the equation, which would be much easier to do with pen and paper and a visual, but just take my word for it. You can do it trivially yourself. You could rearrange the equation because what you're doing is you're basically trying to isolate the inverse of a uh so for the field seven which is a seven is a prime number

and to plug this into the equation if you want to find the inverse of three so your three is a so now you have three to the p minus two which is seven minus two which is five so three to the fifth power is 243 equals three nine twenty seven eighty one two forty three bingo right and so 243 will mod 7 we're 243 equals 5 mod 7 yes and then so you do is yeah

yeah and that so remember we we discussed this a half hour ago where we just said well three times five is 15 which means that those are those two are inverse those are associates right so like how do you use for my little theorem to get to that that's what basically rob just did right it took three to the power of five um what we have the benefit of like we've both been through a bunch of code and a bunch of textbooks that take this property for granted and i don't know

about you rob but i have to be like how the heck do you just tell me that this number to the p minus two is my inverse. I see it implemented in Bitcoin books. And so it's because of this theorem, this property, right? And so he just demonstrated with the number three, let's maybe do an easier example. Remember we also said two and four are inverses of each other. So if I took two to the fifth power is 32, that's a lot easier, I think, to see that 32 mod seven is four.

right 28 to 32 is four right 28 is four from it has a remainder right of four so that's just an easier way to um easier way to visualize it in our mind's eye which is what we're trying to do difficultly on this podcast of course yeah yeah um yes and i mean like it's funny because you could even go to a smaller prime field you could pick the prime field of three if you wanted to you can make these numbers smaller but with the

core equation you can click and move these things oh and i gotta just say if it bothers you guys like i just if it bothers you right now that we just did this and it's not hasn't clicked that's fine i'm like i'm good with that because i'm hoping that just motivates you to just get a pen and paper and do some of these go to the study guy go through the examples and check it like it should bother you that's what that's it's like it should bother you as much as any point this is tripping you up you should be agitated and go figure it out a little bit right it's just the

same way it should bother you that you don't know you don't maybe know if your private key is if your private key is invertible like it you don't really know until you actually learn this math it should that should bother you too yeah right and it should bother you a little bit that we're talking through this. But like, yeah, if you go through this exercise, two to the fifth, and why we say again, two to the fifth, I'm so sensitive to this because I've been through this so many times. Five is p minus two, right? It's a two. So you got, again, remember p to the n minus

one, any number to the n minus one was one, right? So we're pulling that apart. And we're saying, well, we take that number times what? Well, that number times p minus two, remember how you add exponents when you multiply the same number by itself. So p minus 2 plus 1 is your p minus 1 from Fermat's Little Theorem. So Fermat's Little Theorem doesn't give you the inverse. It gives you the property that allows you to sort of exploit that property to find that inverse. It's an extension. It's like an application. But any number in a finite field, modulo p,

you can multiply by that number to the p minus 2, and boom, you get your inverse. And that's going to come in handy when you're multiplying by numbers that are bigger than atoms on this earth. Right Which I think to talk about that as a gateway and to directly touch a little bit a little bit of just how this works in Bitcoin is that we been using very small finite fields 7 17 3 whatever The universe of what we're talking about, though, in Bitcoin is 256 bits, right?

256 zeros and ones and like the size of that universe. that would be really computationally a huge pain in the ass to do all the time but you could already see how unwieldy it gets if my prime is 17 right and i want to just say two to the 15th but i can tell you two to the 15th is going to multiply by two and give me the number of one in that field that much i know i know two to the 15th is my inverse of two I know that backwards and forwards

because of Fermat's Little Theorem even though I do I know what 2 to the 15th is? no I think what is 2 to the 10th? 1024? I can start doing it 1024 2048 is to the 11th 4096 is to the like that's you already kind of see in your brain it's getting unwieldy and that's only the number 17 okay right now you start dealing with computation that a computer can do It's going to get unwieldy at 2 to the 128th power.

Right. It's going to start to get unwieldy. Yeah. Right? Exactly. And so there's ways that you can further kind of chunk this up, so to speak. So it's something that computers can do. And this is also really important from a security standpoint. The reason why Satoshi started with 500 lines of the LibSecP, well, of the LibSecP part of the code base, and it turned, well, the SecP operations. Avid podcast, Magic Internet Math superfan, Richard Hart.

Yes, yes he is. Last two weeks ago, did a very correct technicality call out of what I said. I was being very short and fast with my explanation of the SecP 256k1 curve. That is not the LibSecP library Bitcoin uses. The LibSecP library is kind of think of it. If SecP 256k1 is like this theoretical like field that we use all of our public private key math and Bitcoin around, LibSecP is the execution and implementation of how you work

with that. And that actually didn't come to exist originally in Bitcoin. um satoshi was pulling in i think from like an open ssl library originally and that has problems and concerns because the level of care you would put for securing web traffic is different than if that library was securing money there's a different threat model involved and so the problem is is that you need to compute this like a to the p minus 2 mod p but p instead of being 7 is 2 to the

256 not 256 2 to the 256 so 2 times 2 times 2 times 2 and you get this number that's bigger than is it 2 to the 256 minus 2 to the 32 minus 977 yes so i did a little bit of a shortcut there It's 2 to the 256 minus 2 to the 32. Just saving us from having to explain another correction next week. We talked about this last episode. It's 2 to the 256 minus 2 to the 232 minus 2 to the 9 minus 2 to the 8 minus 2 to the 7 minus 2 to the 6 minus 2 to the 4 minus 1.

I think that's 977. That last piece is 977, I think. So there's 77 digits. The number has 115-79208-92008, and it goes on for 77 digits. But the distinction, though, is because a general hash function only uses 2 to the 256, right? Yeah, and that's exactly right. So when you're doing these operations, they're kind of constrained and bound within that. By the way, I got another correction I should just mention while we're doing the errata section of the podcast.

Yes. Because I posted the video series to Stacker News and somebody gave it – Dude, shout out to fucking people who give these corrections, by the way. Shout out Richard. I wish I had your username. Shout out Richard Hart. But also, this is like, dude, this is like Hart talking about, Rob and I are not, we're trying to create a conversation and we'll miss some things and maybe, so I think the correction I got on Stacker News was the, and it wasn't on the podcast, it was on the video, but the video is based on everything the podcast is based on, was that the K and

the k meant cobblitz curve in sec p which it was a very fine distinction and i'll be honest i don't fully understand the distinction but there is a distinction here with the k in 256 k1 not exactly meaning that it's a cobblitz not necessarily exactly meaning it's a cobblitz curve this is something i was i don't even know if the correction is true but i was corrected but But the correction was triangulated by another Claude call somewhere down the line.

And I was like, oh, that guy's probably right. Yeah. Yeah. No, don't trust Verify, including us guys. Yeah. So for the moment, before I make a bunch more of additional errors, we'll conclude the errata section. But we'll do another one in about 90 seconds. So you have this really big number, which I just fully listed out before. 2 to the 56 minus 2 to the 32 minus 2 to the 9, whatever, right? We need a good word. We need to need a good word for this. It's the Bitcoin number. It's the Bitcoin Prime.

We call it the Bitcoin Prime. It's the Bitcoin Prime. That's a great name for a slop account that does news, the Bitcoin Prime. The Bitcoin Prime. I like it. I like that. Yeah. So your finite modular prime field is this massive number. one that you're not going to be we're not going to try and manually calculate one of these out but what you can do it's really interesting um is that it's a binary number right so if you have zero and one and then you just each each additional digit in binary is a new power of two so zero

right is just zero one you could have as the number one but then you add the next number so So now you have one zero in binary is the number two. The number one one in binary is the number three. Yeah, let me also just mention here, if you've gotten this far, that on my website, on magicinternetmath.com, there is a game. There's two games, actually, that I think are really cool and useful,

and you should go. There are four skill building. One is called Modular. it's a racing game doing modular arithmetic and um it progressively gets harder with like we just did like the first level is like mod five and then he goes to like mod 17 and then maybe mod bigger numbers but like um so it's like you can play against computer play against your friends and get points and build skill doing modular arithmetic and another one is base i'm doing it's conversion of binary decimal and hex and i think at the design the thinking there is just get this would

be a lot more fluid and easier conversation if we didn't have to like explain binary arithmetic all the time so like it'd be good to know that like just off the top of your head 10 10 101 0 is the number uh is number 10 right it's just like 101 1 is number 11 decimal and like i think it's just helpful if you do enough of these and i i made the game for myself like i remember of coding this in Florida and on the flight home, all I did was play this game over and over again,

doing these binary conversions. And it's very helpful to see a four number binary and know exactly what number between zero and 16 or zero and 15 it is. Yeah. And so this is to tie that, I think being fluid in all of these different units that you do operations in is pretty important. And the way I would tee this up to make this like a problem, because I started going down binary, which is a different representation of numbers. But like what's actually really interesting here, let's say if you wanted to do 3 to the power of 8.

3 times 3 times 3 times 3 times 3 times 3 times 3. You do it 8 times. And I'm keeping it as a small number to explain when you get to really, really, really, really big numbers. 64.01? Right, like how big it can go. That's my guess. That's just my guess. 64.01. 65.61. 6,561. 561. But what you can do though is a shortcut instead of doing three times three times seven times three, just start grouping them together and squaring them. Three times three is nine. Cool. And then you have nine times nine is 81. I tried doing 81 squared. You just did three to the four.

Yeah, I tried doing 81 squared in my head and I failed. Yeah, so 81 squared is 6,561. So instead of you can do three squarings instead of seven multiplications. And it's like three versus seven, That's not that big of a deal, but we're still dealing with small numbers. When you start getting to the number of just actual, like if you did it at these large, like the Bitcoin prime number, how unruly it gets quickly. Well, here's the power of that, right? If I said you're doing mod 10, right, and you said what's 3 to the 8th power mod 10, then I already know 81 is 3 to the 4th, and that's 1.

So again, that's like my – it's not Fermat's little theorem. This goes into – it turns out that Euler generalized Fermat's theorem if your modulo is not a prime. And it's brilliant. And I have videos buried in my – it's got four views. But it's a really cool video of me actually sitting there and doing all that math and showing you how Euler generalized with the Toshin function, generalized Fermat's little theorem for – if your modulo is not prime.

then your finite you're sort of like what your analogy to the finite field is now it's it's a group of units that you know has inverses well this is where the grouping gets really interesting right so we're getting to this like bitcoin prime number which for the sake of conversation it's not two to the 256 but you're doing two to the 256 minus two to the 232 which is infinitesimally smaller comparatively it's effectively in the scope of being similar to two to the 256 because the things you're subtracting away are just infinitesimally small compared to the scale of it

um what's interesting about this is that it very nicely starts collapsing on itself if you are doing the squaring trick that i explained where instead of square multiply yeah well yeah exactly instead of doing two to the 256 multiplication operations you can square and multiply 512 times and that's something that a computer can do 512 mathematical operations trivially fast yeah by the way i'm really struggling right now because i want to i feel like i want to rename the

podcast the bitcoin prime that's just a whole nother whole nother issue that i'm dealing with in the back of my head right now so okay anyway um i struggled with this algorithm square multiplier a little bit except the only way i kind of like reconcile it for myself is when i think of um by the way this is all this is all euclidean algorithm everything we were saying before It's just a way of unpackaging and repackaging the process of the long division. What makes sense to me – like I always struggle with bit shifting except when I think of it in decimal and multiplying.

I always know that multiplying by 10 adds a zero, right? Right. Well, in binary, multiplying by 2 adds a zero. This is like – that's the only way I reconcile that in my head is like that multiplying by the base is what adds a zero. Right. Right. Well, this is where I started with binary. The reason why is because this basically the square and multiply trick is leveraging binary representation. And this is something we also, I think, briefly touched upon last episode is that the reason why the LibSecP library exists and we're not using Satoshi's original code is that when the math is actually the money, you have to take a different security posture than if I'm securing my website with an open SSL library.

One of the ways you can attack a system is called a timing analysis attack. And so if you are able to, if you're sitting on a computer and you're able to see the CPU usage and you're able to see exactly how it's spiking and how it's computing all of these numbers, you can start inferring what the actual number is. And if you know the number, you know the private key, right? and so the way the libsec p library handles this the reason why i was going with binary is because like you said every time you multiply by 10 you add a zero at the end every time you multiply by

two you add a zero at the end if you're doing binary representation you can take this number as 256 zeros and ones and you can just work on each of those um the way libsec p 256 k1 gets around this is that no matter what the number is it oh it basically does a bunch of extra garbage math so that it looks like it's taking the same amount of time no matter what the number is yeah let me ask you let me try something here this this notion of a timing attack is the equivalent

in cryptography of like knowing that the word the is a very common three-letter word and being able to say well my i don't have to brute force everything here because i can actually i know that e is the most popular letter and i know that i can try to substitute that and get a good clue as to how i can eliminate a lot of them a lot of the brute force math just by knowing those facts so a timing attack is sort of a similar way of yeah reducing the computation it takes to to

if because you're giving those clues i'll do a rare throw out to pop culture here and if anyone's familiar with the movie uh like the enigma like enigma with the basically alan turing and the basically the war effort to decrypt all of the nazi communication in the movie they have like the aha movement where they realize every single cable that the axis powers are sending starts with heil hitler and because it says that they reverse engineer and say wait a second we know for a fact

they're always starting with this and they use that as a way to start deconstructing and understanding the rest of the message that's being said and because of that they're able to basically break down the entire thing that's a version of like in a way a timing attack yes so that's that's really it so it's the ability to essentially you know completely reduce a lot of the computation that would otherwise be brute force because you've introduced a pattern yeah and the right i'm realizing i'm waiting for the southern power of the law center to put me on

their hate list because i just said that on a podcast like no you know what you've done i this is not to get too inside this podcast is getting deep monetized now no losing my career no not at all it's the other way around i've done this before because you know i'm a jewish guy and i talk about this stuff sometimes this podcast is over well we i have my some of my podcast partners have a theory that's like i've triggered the massad um machine to to and so because we've seen some spikes and downloads in certain episodes where we ended up talking about that and we're

like what the hell why is this happening so um you might have you might have sparked i might i might have got a spike in downloads you might have hit the aggregator on this one yeah for the cia massad everyone listening send some boosts especially right now right i mean although it'd be hard to it's it'd be hard to be noticeable now in um but we this is like two days after the iran attack and everybody hates um jewish people in the world because of it i think they did before the two days ago but also now they didn't yeah but now it's like well the noticing is definitely up there

right now and uh so they might be they probably extended the podcast i think you might have helped the download count there you go perfect great but anyway that's the example of a timing attack right you have you have fingerprinting that you're able to always determine a single look at and be like oh if you're always starting with this or your point like e is the most common letter right and with the way the lipstick library the lipstick p56k1 library ultimately handles this is it adds a bunch of noise and so that every the computation for every number on the elliptic curve looks like the same amount of computation no matter what and that was not part of the original

library because they were using the open ssl library to secure websites and stuff it wasn't securing the money but this is the stuff that everyone leverages and uses when they're actually using bitcoin most hardware wallets import this library as how they do their signature operations this is another example of why you don't want to roll your own cryptography most of the time because the moment you're like oh i found a shortcut it does it even faster and then you realize like you're not doing constant time computation and anyone who's sitting on your machine can infer what your number is is like not a great spot to be in yeah so it's worth

first probably worth glazing because we want to get these guys in the podcast it's worth glazing glazing tim ruffing and uh jonas nick a little bit and the like you know it's a double-edged sword we talk about here because you know one of the reasons we've all gotten away with not being karens at the bitcoin store is because these guys did all the work these guys are the managers and they're doing good they did the good work already to make sure that we didn't have to ask these questions, even though what Rob and I are doing now is saying, well, let's back up a

second, man. These guys have done good work, but are we always going to live in that world where those people are doing good work? I mean, we are adversarial by nature, and we should be, and we should have the ability to know when to glaze these guys and say good work because we can see what they've done and understand it versus saying thank God for being benevolent dictators. Exactly. Exactly. Right. So like, I want to point out, I want to make sure that that's clear and that we, you know, again, having the agency to say good, good call guys. Like, that's the kind of thing you only get at the end of the suffering through the end of this podcast. This is a nice job, Tim Ruffing.

yeah right yeah especially like we're i think we're getting to a point where i think we've just about gone through all of chapter two we did a little bit of a sprinkle uh candy at the end for those that wanted to understand how it works with lipsec p the library itself in bitcoin um there's every single step of this library you could do a whole hour and a half long podcast talking about the nuances and how they put the thought into it and it's a

culmination of a decade of work um we covered a lot of chapter three two here but we what we've stopped where we've stopped short where we'll probably pick up next time if we don't have if we don't have our guest already where we stop short is the discrete log problem right would the discrete log problem be a good spot to do solo so we're not bringing someone to do that and then we can tee it up. I'm going to be at Op Next since now March 1st.

And Jonas Nick will also be presenting there. We should try and just do a live rip. That's a good idea. Let's see if we can finagle that. Op Next is April. I'm looking at it right here. 15th or something like that. It's in the middle of April. 16th, okay. April 16th. Thursday, April 16th. I'll be in town in New York City if you're going to be there absolutely and that would actually give us one more, I'm looking at the date

that would actually give us two more podcasts before we do a live show with him so if we could actually figure out what we do if we get his scheduled permit and work for it, he said he was interested in coming on but I didn't realize that if we're all going to be in the same room it'd be really cool to just rip for 90 minutes and maybe you and I can do a pilot live rip when we're in Nashville when I'm in Nashville because we don't know. I do five podcasts. I don't do a lot of live rips. I don't even know if I have the technical ability right now so we can prepare for that.

Yes, I would like that a lot. That'd be great. And I should be getting just back to the National for Grassroots Bitcoin just as that's happening. God, what a month. April's sick because we'll be in Nashville, we'll have Opnex, and then we'll be in Vegas. Yeah, it's going to be a busy... maybe we'll do three live rips yeah and bitcoin plus plus is happening before vegas um i maybe and then there's a fish show we're gonna start there's a fish show there might be psychedelics

and math and combining everything together yeah this might be this might get out of control really quick but um yeah dude this was cool this is great i like this banter a little bit at the end because we just need to kind of like land, just land the ship a little bit. We just went through, I think a lot of people just went through something kind of difficult and possibly injurious. Absolutely. And the reality is we are just, it's baby steps. We have a large driveway to shovel and it's baby steps.

And we just want good form and understand where we're going. Whether you like the analogy of knitting a sweater or you like the analogy of navigating the iceberg, this is about developing an ethic of spending a little bit of time every day on this and eventually building something substantial, substantial bedrock of your foundation. Agreed. Yeah, just listen to the podcast, go through the study guide.

I think the once every other week cadence for these episodes is a good way to like find an hour in every two weeks just to flip through this stuff and then listen to the podcast. Like it's a good way to, you know, over the course of a year and if you find a podcast later, just start doing that rough cadence. So you get a chance to retain information, think about it. Yeah. Trying to provide a good way for people to get as like a ladder to get brought up into this. That's right. So just keep grinding, keep climbing, and we will see you in two weeks.

Two weeks. Peace.

Open the transcript file

Hosts and Guests

Nobody is credited on this episode yet.

Credit the people on this episode

Be the first to rate this episode

More episodes

All episodes
  1. Exponential Got Less Exponential

    Nov 2, 20261 hr 10 minAudio

    In this episode, we picked back up on our red-team tour of Bitcoin cryptography and tried to make sense of the last few weeks of fast-moving math news. We unpacked why the recent excitement around the exponential time...

    Credit the people on this episode

  2. Red Teaming Elliptic Curve Cryptography

    Oct 11, 20261 hr 27 minAudio

    OpenAI just dropped roughly 300 math papers with Lean proofs, mathematicians are crashing out, and the vague-posting has started: "math is breaking, so cryptography is next." Brian and Rob Hamilton refuse to hand-wave....

    Credit the people on this episode

  3. Hash Functions, Linear Algebra, and Alice in Wonderland

    Sep 28, 202650 minAudio

    Magic Internet Math: https://www.magicinternetmath.com/ Shout out to https://x.com/uncleJim21 for the Alice in Wonderland story and the following rebuke of Lewis Carroll: https://www.youtube.com/shorts/33FYXpEWgyA This...

    Credit the people on this episode

  4. Kayfabe Math is Now Mainstream

    Sep 13, 20261 hr 17 minAudio

    We’re back because math keeps refusing to stay in the classroom. In this episode, I unpack two very different kinds of “math pop culture.” First, we revisit entropy, seed generation, and wallet security through a...

    Credit the people on this episode

  5. Legalize MATH

    Sep 2, 20262 hr 2 minAudio

    Magic Internet Math is back. After the summer that set the Bitcoin world on fire - the Cold Card entropy disaster - Brian and Rob Hamilton (AnchorWatch) reunite for a two-hour deep dive on the event Rob spent three...

    Credit the people on this episode