Cryptography of Ethereum | Lesson 2

Okay, thanks David.

Yeah,

and welcome back everyone. I'm I'm glad to see many of you came back. Um uh uh we will continue um from less time and also touch a little bit of in in um cryptographic applications just to to uh hopefully keep you more motivated to uh study the mathematics. Um uh yeah, what um was that?

Hope you can hear me guys, but it's a bit noisy. Um

um yeah, let me see if I can enable the closed captions. Uh but uh let's I'll give it two three more minutes for maybe before we can start. Okay, it says please start the caption in the chat. I'm trying to I'm trying to find where that is. So, I see closed caption here.

Where is this? Looking for the setting now. at least I can see you click on the three dots and you go to the CC option uh close captions I can see in the or like in the right uh there's the chat on the left and there's CC option Uh, sorry. I I didn't really hear that. You said on the on the chat on the left, I I see there's caption and it says translate to original and English.

Is that what is is just keep that open. Is that good? Maybe it's good now. Okay. Okay.

Harvey said it's good to go. It's all right. Um, so like people can individually

Yeah. Yeah. Like people can individually chose to see the closed captions in the left box. Yeah.

Gotcha. Okay.

Okay. So we can start.

Yeah. Should be good. All right. So, thank you so much.

Okay. So, um I remind you that um we're we're doing a some mathematics uh that is quite involved and h I want to encourage you to ask questions. I mean even even if it's a simple questions you can ask during during the session I I like to have as many questions as as possible. So even if you just want to make me happy just ask questions. Um, and last time we talked about uh groups and and a group is is basically um a set with a binary operation and a neutral element satisfying some some axioms.

And we also talked about fields. And the main example we gave is um you take a prime a prime p and you look at um what is denoted as FP which is all the numbers which can be obtained as remainders. modul and on this this set you have a addition modul and multiplication model. The neutral element with respect to addition is zero. H and the neutral element with respect to multiplication is one.

And um in the in the questions that uh that happened at the end of the session uh somebody asked why why should we care about this this FP and I began to g to give an answer but I I want to extend the answer uh now. So and the main theorem that leads to the this application is that if you take FP and you remove the zero element, right? So you have one up to p minus one. Um and you consider this operation multiplication modul. Then by the axioms of of a field this is a an abilion group.

But the theorem tells you that this is not just any a billion group but rather a cyclic a billion group. And what does it mean? It means that there exist at least one a generator in this in this set I mean one number between one and p minus one such that fp star can be described as all the possible powers of the generator. So g to the 0 which is by convention 1 g or g to the 1 g² and so on until g to the p minus one. Okay.

Uh sorry p minus 2. H so you see we have we have P minus one elements here and all of them are some power of P. So or in in other words for any X in FP star there exist some K between 0 and P minus 2 such that X is G to the to the power of K. Now this this leads us to what is called the discrete logarithm problem. Um the problem itself I I will state it without any uh any um explicit parameters.

Um that is if P and G are uh known. This is usually referred to in cryptography as as public. All the all the people involved in this question can know P and uh PNG and X is chosen randomly from FP star then it is hard um to Find k as as before such that x is g to dec and the re the reason it is called discrete logarithm problem is because you you know you know that x is equal to g to the k for some k. So if you had like a log on basis of G and you could you could apply it then it would be it would be equal to K. So you could com compute K if you had some kind of a um a hypothetical login basis G function.

H now what does it mean hard? hard. It means that it's hard relative to the the size of of P. And usually we we measure the size of P in um a number of number of digits. Number of digit digits is almost the same as number of bits.

You know there is some factor because we we count usually on a decimal basis and not on on binary basis. But up to a small factor they they are the same. So a um hard here really refers to or relative to the length of bit let's say bit length of p and it is it is common it is common assumption This is what is called the hardest assumption in cryptography to say a for example if a a p um is a say has a 248 digits then a a DLP is is invisible. even with a superco computer, even with a a several hundreds of years or something like that. On the other hand, if you give me um G and K of course and of course P then it is computationally feasible.

to compute G2 dec G to dec mod P, right? Because we are in a a in a car in a field or in a field FP. So we need g to the k mod p in order to go back to the field or to the the field without the zero element. So so this is a classical example of a um one oneway function. I mean if you give me G to the if you give me G and you give me K I can calculate it may take some time but it it is definitely feasible even on a regular computer to compute G to the K for such such a big prime number P.

But after I give you the result, it's very very hard. It's in fact invisible to uh to come up with the with the K that made this uh made this element G to the K or X. And under this hardness assumption we have a cryptographic protocol and this is called defy helman key exchange. So before I I I describe it, I just want to say I mean cryptography is um is not just about sending secret messages. It is maybe the the study of um a a a wide variety of what is called primitives that um preserve a privacy in some sense.

But this is a loose definition and there are many different kind of cryptographic protocol that have nothing to do is sending a a secret message. H nevertheless this Dy Helman key exchange is is a a primitive towards a being able to send a secret message. And the problem is is as follows. So you have Alice and Bob living in two parts of the world and they can only communicate through the internet and they want to agree on on a secret. This secret is is a secret key.

Once they have a secret a secret key they can agree on then they can e use another protocol to send encrypted messages to each other. But first they they need to agree on a secret. And since they they can only communicate with in the internet, they must assume that everybody can can listen to the communication. So they need to So D Helman key exchange protocol is is a way for Alice and Bob to agree on a on a common secret by means of public communication. And the way it goes is is very easy.

Um so Alice chooses um secret or or uh sorry before so they need to agree before before they start the protocol. Um, Alice and Bob um by by public communication agree on M prime P with a say two,48 digits and a generator for um a FP star generator G i.e. G is some number uh between 1 and P minus one and G generates by if you take powers of G modulo P uh you get the entire FP star. These these two things I mean choosing P and then choosing such a generator are computationally feasible problems.

um choosing P like is this you probably all of you or most of you know how to do it efficiently choosing G is slightly more involved but it's not a big deal and they had to do it publicly so they you know it could be that Alice chose P and G and send it to Bob and and Bob simply checks that G is is a indeed a gener that P is indeed a prime and and is indeed a generator for FP star but anyone who is listening to the communication can can also see it. Okay. So these are the the public parameters and and now the protocol begins. So Alice chooses secret s Alice. S Alis is a is a number between H well it's it's just a number between one and P minus 2.

or in fact zero sorry zero and p minus 2 at at random. So, so the notation here, the typical notation is that S Alis, the secret that Alice chooses is taken at uniformly at random from um a zero up to P minus 2. and and and then or also Bob Bob does the same. Bob he chooses the S SB uniformly at random from zero up to P minus 2. So, so this is a you know this is Alice let's say and this is Bob and we said that E the first thing is that Alice takes a secret uh how do we call it let's call this this group I call it big And Bob takes a secret at random from from the the the set of secrets.

S and then because they agreed on a generator, Alice can send to Bob, we can call it Xalis is well G to the S alis modul P. So Alice computes g to the sa modul p. This is considered feasible and sends x x the result sends to Bob and we call this result x x alis and Bob does the same. He has he has a the secret that he chose at random and he computes xbob which is g to the s bob modul and he sends it to. So a after the the the two rounds, Bob has X X A and also SB and Ali's has XB and also SA and the common secret is um G to the X A * XB.

How do they compute it? Well, Alice has X to the B, which is presumably if if Bob was honest, H it is G to the SB. But Alice also has E S S Alis. So she can take xbob and raise it to the power of s alis and this is by definition g to the sb to the sa mod p. But this by the axioms of um mod p multiplication this is the same as g to the s the sa * sb.

Oh I uh uh I mis wrote here I apologize. The com the common secret is g to the sa times sb. Okay. So you see Alice can compute the common secret with the information she has and Bob can also compute the common secret because he has X Alice and he can raise it to the power of S Bob and this is G to the H S Alis to the power of S Bob and this is also G to the S A time SB. Now what happen?

Now what about the security? So we assume that the discrete logarithm problem at this size of the prime is hard. So an eavesdropper let's say this is a Eve. She's an e eavesdropper and she she can see xa but she cannot find out what is what is sa even though even though she knows what is a g and p and she can also see what is xb but she cannot figure out what is a what is sb because again she cannot solve the discrete logarithm problem. Now you may say, okay, but if she has X A and XB, she can multiply X A and XB.

But if she multiplies x A and XB, what she gets is G to the power of S A* G to the power of SB, which is G to the power of S A plus SB and everything here is is mod P. So the an ifs dropper can listen to the communication and and calculate this quantity G to the SA plus SB but it it cannot find out what is G to the SA time SB and Alice and Bob each of them has has the information to calculate SA and SB. So that's that is considered the the common secret. questions. I see there is a bunch.

Yes, there were some answer in the chat already.

Yeah,

I think you um

how can how can we find out if G is a generator? Yeah. So I didn't say it but one way I mean you you fac you you factor G to a product of primes. Let's put it in green here. G is is just some number between one and one and P minus one.

So you can factor it to a product of primes. Let's say pi P I I equals 1 up to L. Okay. And then you check that g to the p divide p minus one p minus one divided by p i is not equal to 1 modulo p for each i and if you have that then you know that g is a generator. So this is a there is an algorithm that does it for you.

Again, there is a there there's certain ways to to make it a bit more efficient, but generally speaking, it is it is it is efficient. Um what else? H no that's not true that any point is a generator h because cyclic group is not always generated by a by any element I mean take for example um integers modul four it is not generated by the element two you do two two + 2 is four which is zero and that's it anytime any number of times you add two to itself 12 you cannot you cannot get to three module four um in a field with p = 7 g = 2 doesn't work to generate the whole field I don't understand there any size constraint on g the size constraint on g is is is basically the size constraint on the the prime number right g is of size p minus Yeah. And if you take P to be too small, then of course then the discrete logarithm problem is not that hard. Uh how does defy helman works in an elliptic curve group?

That's that's out of scope for now, but we I I I very much hope to to get to elliptic curves in this series of lectures and we can discuss it then. Okay. So, I hope you're you are motivated a bit more now to see that the the the mathematics we do has has a a very practical application in in the cryptographic world. And um this of course remain I mean should be also the motivation when we start talking about curves and so on but I would like to keep it as as simple as possible for now. So the definition I want to talk about is now so if you have a field Um then the characteristic of the field let's say a um a finite field.

Um the characteristic of f is the minimal number such that the minimum number uh um C such that 1 F plus itself C *S is equal to zero and uh the the the stress here is on the minimal. I mean there must be there must be some number. Um just a second I'll um I'll be back soon. Um, so you see obviously a if you have a finite field then a a one + one has to be different than one. H and 1 plus 1 plus 1 has to be different than 1 and 1 + 1 and so there is only finitely many possibilities that you can cover in the in the field.

Uh so at some point you have to have a a a number of of ones that you add to it to itself and gives you zero. That's that's the let's say the uristic. Um and if If f is infinite we say we set that the characteristic of f is infinity. So for example the the real numbers are considered to have um infinite characteristic and the first proposition maybe observation is um for finite f R F is always prime um let's let's call it P and what um what is the reason otherwise um car f if the characteristic of f is um is not a prime then it is let's say a product of two integers k and l with um bigger than one then I I do 1 + 1 k times and 1 + 1 L*s and this is if you look if you use the distributive law H which is an axiom of of a field Um this is a a 1 + 1 k * l * which is we assume this is this is the characteristic so it is it is equal to zero but on the other hand these two numbers are not zero I mean k cannot be zero and l cannot I Maybe we call it k subf. This is this number and this number is l subf.

When you you add the the unit element of the of the field l times each of these numbers cannot be zero because in a field if a product of two elements is zero at least one of them has to be zero. But k KF cannot be zero because it will contradict the minimality of characteristic. And remember characteristic maybe can write P here is the minimal number such that if you add one to itself this number of times you get zero. And if k e is already zero then since k is is smaller than p then it contradicts the minimality of of the characteristic. So um here we say m um and kf and lf are different from zero by a a minimality of the characteristic and so that that's a contradiction.

So this if if we assume towards contradiction that the characteristic of of the field is a a product of two a non-trivial product of integers then we we get a contradiction. So this means the characteristic of f is always the characteristic of a finite field is always a prime number. And we know we know that for any for any prime number we have the the the prime field FP. But the question is whether there are others can there be other fields of characteristic P that are not exactly FP or not exactly FP up even up to isomorphism. Right?

We didn't we didn't define isomorphism of fields but it's a it's exactly it's exactly analogous to isomorphism of groups is like if the the addition and multiplication tables of um of of the two fields are are the same up to a change of notation up to a change of names. So here's an example. I take um we we will call it now GF GF4. GF4 as as a set it has four elements zero, one, two, three. And the addition the addition table of of GF4 is um is the same as um same as integers modul 4.

Okay. So you know one sorry 0 1 2 3 0 0 1 2 3. If you want to do uh 2 + 2 that's that's zero. And the multiplication table is a bit is a bit more tricky. Uh well you multiply everything with zero.

Anything with zero you get zero. You multiply anything that is not zero with one you get you get the same. And and now for the rest it's 0 2 1. Okay, that's a multiplication and as an exercise you you can check that this is a field. I mean to see well obviously since integers module four is in a billion group.

So this this e the add like addition the addition of this field is is fine if you want to find the the multiplicative inverse which is usually the uh the problem. So multiplicative inverse of one is one. Multiplicative inverse of two is I need to multiply two. Wait. Um, yes, something is off for some reason.

I think I I um I copied it uh wrongly from somewhere. Now this let me just uh quickly Google it. Um yeah. So two two. Oh yeah.

So this it this needs to be one here. This needs to be two. Yes. Uh I'm sorry. I um I had a typo in my notes.

Um but but you see so if you want the the multiplicative inverse of two is three but the h and the multiplicative inverse of three is uh is two. H and observe that um this is not multiplication modulo 4 because I I take for example 2 * 3 uh this is six module four this should have been two so this multip the multiplication table here is is h you know is not modul four somebody thought about it carefully and h and you can see that this is a field what is the characteristic of this field. Characteristic of this field is the minimal number such that a 1 + 1 is equal to to zero. And since 1 + 1 is is a is equal to uh oh sorry here oh I apologize. Um

hello

yes like 2 into 3 is equal to 6 and 6 modulo 2 is equal to 2 but you put one in multiplication table

I didn't say well I didn't say the multiplication is let me I didn't say the multiplication is modul 4 I I I simply wrote a a a a multiplic a multiplication table. Let me write the

This is wrong. This is the wrong Your multiplication table is wrong.

Uh it could be because you know I I just uh I just copied the copied it from um from somewhere and I could have could have done a mistake but uh let me double check. Uh yeah, let me double check this. No, I think the Okay. So what what we have here as the addition table I mean obviously uh this is uh 0 1 2 3 uh this is 0 1 2 3 and now um this is one one zero So 32 and two. Um yes.

Uh 2 3 0 1 2 3 0 1 and uh here 3 2 1 zero. Okay. So um let me double check the multiplication because you say but I think the multiplication should be should be okay now. So what was that? Of course.

0 0 0. Um 0 1 2 3. Yeah. Um 0 2 uh 0 2 3. Yeah.

Yeah. 023 1 and then 0 312. Yeah. So it should be okay now. I I apologize for this but yes.

Yes.

Why? Why 2 into 2 is equal to 3?

There is no why the I present to you uh addition table and multiplication table. This is it's a free country, right? All I have to do is show you that the axioms of a field are satisfied. There there is no why the the question why in definitions is I mean you know of course now if you ask kind of how did I come up with it okay that's a different question in this in this capacity you in this size you can imagine that I just tried all the options it's not so many options and I h stumbled upon addition multiplication tables like so and I checked and the axioms are satisfied. Okay.

And you can check you we we checked by hand um multiplicative inverse and observe that the characteristic of the field is two characteristic of GF4 is equal to two. Okay. So um we have a a field of characteristic two that has four elements. I mean obviously it cannot have a characteristic four because we know that the characteristic of a field has to be a prime number. But on the other hand we so far we only knew about fields of characteristic two that have two elements.

And now we see a field with four elements. So this this should drive the the the curiosity to to find out how can we construct a new fields of characteristic P. Any other questions? Okay. So um polomials this is this is now a detour but uh it's an important detour even in in its own right even um for many many other applications you need to know a stuff about polomials.

So um let f be a field a polomial um over f is a formal expression. Let's write it like this. f x equals f_sub_0 + f_sub_1 x plus f n x to the n where um the fi so f0 up to fn um are elements in the field h and Um let's say by convention we we assume that if we write it like this then fn the the last one is non zero because otherwise we we can just omit it and n is called the degree. Let me let me simply write it like this. A degree of f the collection of all polomials over f.

um is is denoted as a f I mean if you take variable small x then it's denoted as um f with a square brackets x and f with square brackets x and less equal to n is all polomials um of degree less or equal to n. And here let me just introduce one a a one less a a a type of writing. Instead of writing this long expression, we can write a sum i = 0 up to n fi x to the i. Okay. So that's that's a polomial.

What does it mean formal? Formal means that two polomials f and g let's say f is um sum f_subi x to the i = z up to n g gi x or Maybe say Gj X to the J J equals 0 up to K are equal if and only if N is equal to K. So they have the same degree. And for every i between zero and n fi is equal to gi. Okay.

So the so so formality formality here really refers to to the notion of equality between two polomials and and maybe the the biggest warning that you should have with regard to polomials. A a polomial is not the same as a function let's say um fbar from from the field to itself. Even though every polomial so every f gives rise or induces um a unique function that we by abuse of notation. Many people denote it as still a steel as f but here let me distinguish it and call it fb bar. Fbar, it takes an element A, plug it in to the polomial instead of the formal variable X and uh calculate what what you have in the expression and and get some element in F but not conversely.

I mean for example f is equal to the prime field f_sub_2 which is just two elements zero and one. The number of functions h between f_sub_2 and f_sub_2 is only there are only four possible functions but there are many many many more polomials in fact there are infinitely many polomials over f_sub_2 because you can always take x to the n where where n is some uh some number so so pol so this this is an important distinction a polomial gives you can induce a function by by substitution but it's not the same as a function and uh it's not the same exactly because um because of this this formality property. Now we have two we have a um or operations natural operations on polomials one is a is addition you give me um let's say f and Then uh of course it's it's like you you you add expressions that you you you had in uh whatever equations in the high school I mean the the sum of f and g or what is called so so add let's say h for simplicity maybe we do it m and n and let's say that m is a a lesser equal to n Then um f(x) + g(x) is simply a a sum up to the smaller the smaller value. So let's say k is equal to uh zero up to m fi f sorry fk plus gk x to the k plus a and the last part is is only um is only g. So plus sum m from k = to n + one up to n gk x to the k.

Okay. and multiply it's it's a bit more you know the formula is a bit more involved I I can write it down just for um for you to to look look it up later on but of course intuitively should should be very clear. So f(x) * g(x) uh is going to be equal to sum c k x to the k equals 0 up to n + n. And ck in itself has a has a a bit of a convoluted formula. It's like this ai, not ai fi bj um where i runs up to n and j runs up to n and i + j is equal to k.

Okay. But of course you you can just take you know take a polomial x² + 1 if you want to multiply it by x cub + 2x + 2x + 2. Well I mean you know you just open the brackets and you you get some some polomial expression. Okay. and and then there is there is another another operation but I think that that one is better to save for after the break.

So maybe it's time to take some questions and then um um 10 minutes break. Okay. So maybe before I introduce the the next operation, well let's do an an example. So the the next operation is um is long division. So I give you a a two polomials.

Let's say f is equal to the real numbers and you want to divide uh 6 x cub - 2x² + x + 3. This we call f by h x² - x + 1. This I call g. But like like integers sometimes polomials just don't divide each other. So we want to do a division with a remainder.

What do we do? We take the leading guy here and we divide it by the leading guy here. Um what we get is is 6x Uh so 6 x is uh 6 x cub / x². We put it here. This is a part of the result.

And then I do I take this 6x I multiply it by this guy x² - x + 1. I get 6 x cub - 6 x² + 6 x and I subtract the result from the h from the polomial f. What do I get? I get that the leading coefficient of f disappears. This this is by design, right?

And so I get - 2x^2 - - 6 x² that's 4x² - 5x + 3. And now again I take the leading coefficient here and I divide it by the leading coefficient here. The lead the leading monomial I should say. Well what do I get? I mean uh 4 x² divided by by x² is is 4.

So I put m + uh 4 which is 4 x² / x². Okay. And then I I take this uh this four and I multiply the the polomial g by 4. So this is 4 * x^ 2 - x + 1. Um and the result is 4x² minus 4x + 1 and I subtract again the leading coefficient disappears by by design.

So this is - 5x - - - - - - - - - - - - - - - - - - - - - - 4x. This is - x and then 3 - 1 is 2. Uh ah here it should have been four. So 3 - 4 is - one. And what I claim and you can check uh let's call this guy the the quotient qx and we call this guy the remainder rx and you can check that f is equal to G * Q + R.

And obviously the degree of R is strictly smaller than the degree of H of G. So this is my this is my uh stopping condition. I mean, if if the degree of R would would be greater or equal than the degree of G, then I could do the same trick that I did with the green and the yellow all over again. Get rid of the the leading the highest monomial. And so um so you see and this this is more generally true.

Uh the theorem is um for for any f and g in f x. Note that I I write for simplicity I omit the the variable x when I write f and g this is this is a matter of taste but it is conventional uh writing and uh you I hope you you will see later on that it's it's h in some cases it's more it's more intuitive to to do it this way to write it this way um for any polomials f and g h such that the degree of of g is smaller or equal than the degree of of f. There exist unique polomials q and r unique. unique is always with respect to some some condition. So satisfying the property the two two properties one is that f is equal to q * r uh sorry q * g plus r and two is that the degree of r is strictly smaller than the degree of g.

Okay. And sometimes you you write f many times in in in programming you do you do this notation f divided by g with remainder. So this is the remainder of the uh the entire operation. Any questions about this long division? Okay.

So, so the slogan here maybe well the slogan is that a polomials especially over finite fields um are are like integers. Erh and we will we will expand this analogy but e um this is an informal statement. I mean unlike stuff where we we we make a precise statement and we we have a proof. This is an informal statement that is supposed to give you an intuition of how how we we proceed in in various construction. we will see and and and don't don't dismiss this analogy so quickly I I think it is very very helpful to to think also in intuitive terms like this.

So well I mean one justification for this analogy is that we have long division. I mean we have addition, we have multiplication and we have long division. That's that's pretty uh pretty similar already to to integers. And a another thing we we have is a notion of prime polomials. What is a prime polomial?

A polomial f in um in variable x over a field big f is prime if um it cannot be written is um f is equal to let's say um g * h with g and h polomials um let's say non-constant because of course I mean if you You take the leading coefficient of f. Let's say f is a f is 3x + 3. Then of course I can write f as three * e x + 3 that's not uh or you know it doesn't even have to be three here. can be four for example and then I can write f as as 3 * e x + 3 sorry 4 over three okay so but that that's not an interesting uh that's not an interesting factorization because you can always do that h so but if you can write f as a product of two non-constant polomials we call f a a prime polomial Okay. So, this is this is another another piece of the the analogy puzzle.

Now um maybe a a an important corollery of this of this theorem star that that it tells you that you can always do long division is what is called um well so If f is a polomial over a field and a in f a root h sometimes it's called a zero of f i.e B F if you substitute A in in F then you get the zero element in the field. Yeah, this is this is a root. Then f or there exist there exist polomial fbar in polomials over f with variable x such that f is x - a times far of x Why proof do a a a long division of f with x - a. Now if you do long division this is by definition there is always some remainder rx.

Okay. So I can write a a f let's say fx is equal to x - a times the quotient qx plus r of x and the degree of r has to be smaller than the degree of the polomial I'm I'm dividing by. So it has to be smaller than the degree of x - a. Um but the degree of x - a is one that is the degree of r has to be zero. So so r is some constant polomial where c is c is an element in the field.

Now I substitute a in this in this equation. F of A is equal to zero. Right? And if I substitute on the the right hand side I get that this is R of A because H the first the first sum and vanishes. So I get that r of a is equal to zero but r is a constant polomial.

So, so C is and the the cor the corery of the corery um a polomial if of degree n can have at most n a a different roots or or zeros. Why? Well, I mean if if a1 is a a is a root, then I can write f of x equals x - a1 times uh let's call it f f uh well whatever f f_sub_1 of x and if a2 is a root Then well obviously if I plug in if a2 is different than a1 I plug it into x - a1 that's not it's not going to vanish. So it means that a2 has to be a root of f_sub_1. That means that f_sub_x is equal to x - a1 times x - a2 times some f_sub_2 and so on and I can only do it n times because the degree of f is n and uh these guys um h can can only I mean when they they multiply they can only h reach up to to x to the Is this clear?

This is a this is an important erh fact about polomials. Okay. So we we defined before this uh this uh little detour we defined what is a prime polomial. Um observe any polomial can be can be factored to a a a product of primes. Why?

It's exactly the the the same the same algorithm if you will that you do for for integers. I mean uh you you take an integer. How how do you know that an integer can be um written as a product of primes? You look at the first prime uh two. If two divides this integer then you you you do the integer you know you you start with an integer you check whether it is divisible by two.

If it is divisible by two you take n / two and you continue with the next prime three and so on. And if not you still you continue you you take n and you ask whether n is divisible by three. And since so there are only finitely many primes that are smaller than n. Uh of course it could be that two divides n but several times. So you you you check whether two divides n until it doesn't.

Um and you check for all the primes smaller than than n. And uh eventually you get a a factorization a factorization of n to the product of primes. When you'll deal with a polomials over finite fields, if you give me a polomial of degree n, there are only finitely many polomials of degree less than n or less less than equal than n that can be prime. I check whether this polomial is is divisible by each of these guys and eventually I get to a a product of of primes expressing the the original polomial. Okay.

So this is again an extension of the analogy and now I I I want to use the analogy. So remember how did we how did we um build the uh the field of um the prime field FP. What we did is we we took integers and we took integers modul where we did um I mean integers modul is really we took all the possible remainders of e integers that are divided by p I mean all the mod p e remainders this is zero up to p minus one. Okay, the remainders and on this on this uh on this set we defined addition modulo the prime and multiplication modulo the prime. And we proved that this is a for a prime number that this is indeed uh a field.

So now I'm going to do the same but for polomials I take so let f fe this is like this is like the our our substitution for the prime be a a prime polomial let's say over a finite field I I can even simplify over um well okay let's let's do it maybe over a finite field and then this is this is valid over over any field but um easier to see it this way and now I take um I'll do this. So we said that polomials with variable x this is like this is like the integers right h and f is like the the prime p. So now I want to take I I will write it I will even write it like we we or in a similar way um to to this notation fpx is the set of all possible remainder polomials if you do long division of a a given polomial by fe this is let's say a I X to the I I equ= 0 up to K where K is less or equal well sorry K is strictly strictly smaller than the degree of F. So let's say degree of FE is equal to N. So k is strictly strictly smaller than n which is degree of fee and a all the ais are elements in the field fp.

Okay, this is this is all the rema all the possible results of doing long division um with with the denominator because of course um I mean simply take take any I mean take any polomial in this set R do long division of R by by FE and you get R or if you wish you can do you can take any any polomial in this at r and you can add to it fe * f * something let's say f * x vx * x a and the if you do long division of this expression by f the the the remainder is r so any any so so basically any any polomial of degree less than the degree of fee can be obtained and this is all the pos can be obtained as a remainder in long division by fe and on this on this set FPX sub I I define a addition modul and multiplication moduli how do I do it I take addition modul is in fact just addition of polomials. This is just um just add let's say R1 and R2 as polomials as polomials e because if you add two polomials you don't increase their degree. So the the addition of of r1 and r2 is still a polomial that is of degree smaller than n. But if you multiply two polomials you the degree e the degree of the the result is the sum of the degrees and potentially you know if if um r1 of x was of degree n minus one and r2 of x was of degree n minus one as well then the multiplication is of degree 2 n minus2 which is already bigger than n. So you need to do modulo modulo namely you take the R3 such that R1 R * R2 is um is equal to Q * V plus R3 okay and there is a unique H polomial R3 three that is of degree smaller than the degree of fee that satisfy this equation.

Okay. So we have it's like this is this is a this is the analogous construction to to the prime field and now well so what is the the the zero element here the I claim let's say theorem fx sub is a field. Why is it a field? Well, the zero element the zero element is is simply the zero polomial. The the the constant polomial on on one is is also a remainder.

Let's say um n is is bigger than one. Then the constant polomial is of degree less than n. Then um these guys are legitimate polomials. This is by the way this fpx sub is just a is just a fancy notation to all polomials over fp of degree less than n. Okay.

So this is um assoc associivity. What is what is the um well associivity is is because a modulus is is associative. H what is the the additive inverse? Additive inverse. inverse of um of rx is a v minus rx vx - rx since plus v - rx is equal to vx which is equal to zero modulo Sorry.

Um, so I have I have an additive inverse. What about the multiplicative inverse? So here we have a lema. Um, if let me just pick up the notation I had. If um f and v are polomials over f and f is prime.

Erh there there are polomials u and v over the same field such that f * u + v * v is equal to 1 to one here this is the one the one element in polomials this is the constant polomial and equality is equality as polomials. Okay. So if you wish I I can uh I can write the variable fx vx plus vx ux. Oh, I uh should be I guess u and v. So fx ux plus vx vx is equal to one.

The polomial constant on one and um this lema is another extension of the the analogy between polomials and integers. If you remember, we had the same lema for integers. So you you just replace here you you you can rewrite the statement by keeping the same letters and saying instead of um these are polomials saying that they are integers. And we had a we had another claim that showed that this is this is true for for ordinary integers. Okay.

So if this is true, this is true. And by the way, the the the proof that you have for integers um or for the the the integer version of this lema can again be pushed by the analogy simply be translated to a proof that this lema is for for polomials is true. This is called by the way the the bazoo the bazoo lema. And so using this lema I now want to have to show that in this field x sub I have a multiplicative inverse. How do I show it?

So now remember FPX sub is simply the collection of all polomials over FP of degrees smaller than N where N is the degree of V. Um if r x is some polomial over fp well is some remainder polomial. What is the inverse? Well, since f is prime, a dilemma tells me that there there are polomials u and v over fp such that rx ux plus vx vx is equal to 1. But this means if I now take modul for the entire equation, I get that m rx ux is equal to 1 modulo v because when I take a long division by f of this expression, it it just it has no remainder.

The remainder is zero. i.e. Ux modul is the multiplicative inverse of um of r. Okay.

And the rest of the axioms are very easy to check. It's a it's completely analogous to um to the the construction of the prime field. Now how many elements? So we uh before I move on any question about the the proof I see there.

Yeah.

Yes. So let's see h multiplying a list of n elements roots will guarantee we will get a polomial of degree n. Yeah, if if you multiply x - a i you multiply it n times and this is just look at this. Let's say x - a1 x - a2 x - a3. How do you open it?

You need to to do this times this. this times this, this times this, this times this E. But really what what is going to dominate the degree is is you're going to have an expression X * X * X. This is the the highest degree of expression that you get. So you will get X some polomial of degree 3.

Uh so that's for this question. Um yeah. Okay. Is the additive one of a polomial? Uh I'm not sure what this question I don't I don't understand the question.

The additive one over polomial. I don't know what is additive one. Maybe additive inverse of one. Uh additive inverse of the polomial of the constant polomial C is minus C. So with each element that is not zero with each element in FPX divided by prime um there will be multiplicative inverse of it.

Yes, this is what we showed. This this is guaranteed by dilemma. Uh dilemma dilemma tells you that there is this u and v and u is going to be uh the multiplicative inverse. By the way, I should say I should say again the the full proofs the full details of what I say now appear in the book like everything else. Um so you know you can always and of course it's not the only source um you can always look there but this is this is to give you a um a some sketch of how things are constructed and and what I wanted to get to before we we end this session I mean how many elements what are the number of elements of FPX X F sub F.

Well, I mean I have a polomial a of this is this is the same as I mean polomials of degree less than N over the the field P. A polomial of degree less than n is completely determined by this is the same as as a vector of size n. Give me a vector of size n. Some s some of its coordinate may be zero. That's okay.

Then I give you that it determines a unique polomial of degree less than n. Right? because a polomial has a a coefficient zero up to n minus one. This is a coefficient z up to n minus one. So the number of elements in this guy is is the same as the number of elements in the cartisian product of fp with itself n times.

This is n times which is p to the n So you see that we have constructed I mean assuming you believe me that a there is you can always find a a prime polomial of degree n for any n then we have constructed a field of size p to the n for any n okay this is called the gadwa field. Um the Gadwa field this is this is a field um of size P to the N. Observe that well there there are several things. Erh one is that FP itself FP itself is a subset and in fact a sub field of FP X sub why because a a a I I can consider FP as as constant polomials. Okay.

So you know a a rx may be some some constant c rx here maybe some constant c and c can be any element in the field. So by by this I have fp embedded into the h into the bigger fieldpx sub field. What is the characteristic of the new field? The characteristic of the new field is still P. Even though the number of elements is P to the N, the characteristic is still P because you take the element one.

The element one here is the same as the element one here. You add it to itself a p times you get zero because you add a constant polomial one to itself p times this is p * the constant polomial and uh this is this is zero and the third observation is that I could have done it for any any finite field I I don't need I don't need specifically fp I I did it for convenience because you you know FP but a um FP can be replaced by any field any finite field. Okay. And now for the big theorem. This is a a a classification of finite fields.

um for any prime p and any integer a positive integer n. There exist a field with P to the N elements and any two such fields are isomeorphic. Okay, this is a big this is a big gun and they are denoted GF gala field P to the N. Okay, going back to the Galwa field um that we we kind of constructed by hand. Well, here you can take um let me just quickly Google it.

Uh m I don't mean to interrupt but we already two hours now. So

yes I I I yes I will. Okay. So and I'll just say here you can take a polomial h over f_sub_2 f um it's it needs to be prime polomial h it's going to be I think x x² uh well okay you you can pick a a a prime polomial over f_sub_2 such that you you get this this addition and multip multiplication tables as remainder polomials of of of this but I I uh I need to check the details for uh the polomial itself. So let's u let's finish this uh now with just uh taking questions. So we Yeah.

Yeah. So for for the for Galwa Galwa field four the polomial is apparently x² + x + 1. You need to check that this is this is a a a prime polomial over f_sub_2. H this is true because if you you substitute zero you get one. If you substitute one you still get one.

So this polomial doesn't have any roots and then e a these guys are in fact a just remainder polomial. I mean we call it 01 23 but this is a um the 01 x and x + one and that's this is all the possible remainder polomials uh by division of f. And if you check you can see that the addition multiplication tables are simply I hope I'm not the polomial is is correct you you can check that the addition multiplication tables are simply um addition and multiplication modul modu is our notation. Okay. So, what um um what questions do we have?

Erh Lee, can you can you speak up because I don't understand um exactly the question.

Uh yes. uh during your uh definition uh of the the final part of the notes uh you gave the definition for the color field and uh my question is uh you wrote here yes uh scroll up a little bit yes here you gave the p uh p power to the n uh equal to the

yeah I just lost the number of elements.

Yeah. Okay. So we we want to know so we we prove that this this uh creature fpx sub which is kind of analogous to fp is is a field and now we want to know how many elements does it have. So I I put a a dz here. Okay.

um this as so this is just it's a question of set how many elements in exist in this set here you don't care about what is the the operation addition and multiplication

this set as a set is it's it is simply all polomials of degree less than n over fp right

yes you you follow

uh yes yes yes I already got that part actually thanks And how many polomials of degree less than n are there? Well, you know, you choose the zero coefficient. Let's say you you can say a polomial of degree less than n um you know is a sum sum f_subi x to the i= 0 up to n minus one. This is a kind of a redundant notation because fi may be zero but e for the counting it's it's it's easier to do it this way um and so every every napel f0 up to fn minus one that you choose give give me a polomial it's it's a onetoone correspondence how many tpples I have h and times the number of elements in the in the field FP.

Yes.

Is this clear already?

Yeah. Okay.

Yeah. Thanks a lot.

Uh any other questions? This is really a great time, I think, to tie the the loose ends. Okay. So let me just quickly advertise what what I want to do next time is not exactly cryptography but rather a a a an algorithm. This algorithm is called fast for transform and we will prove the the properties of the algorithm using the stuff we did with finite fields with I think I need a little like a little addition h to the stuff we we developed.

FFT is an algorithm to efficiently multi multiply polomials over a finite field. So instead of doing it in complexity n² if the the degree is n for each polomial you can do it in in n log n and um it is one of the most used algorithms in applied mathematics and especially in cryptography. So it's not a cryptographic primitive per se, but it is a a very important piece for many many cryptographic applications. I think it's a it's also a great a great application to to um to see the stuff we we we talked about in action. So that's next time.

And uh yeah, I hope uh I hope to see as many as as you as possible.

Yes, we will continue next week. Thank you so much, Matan. That was really great. Awesome. Very excited to see the uh the next talk.

Uh for now, I just want to remind everyone that we don't have a session this Wednesday. Uh you can let us know in the discord if you want to do a special office hours in Asian times. Um otherwise we will see you again on Monday for another session with Matan and then we will have Tuesday Wednesday session on the lean uh moved from this week. Uh just a reminder awesome and uh yeah we'll have a recording of the session with all the resources up on the stud wiki uh tomorrow. Very well.

Bye-bye.

Thank you everyone. Bye-bye. Have a great day.