Cryptography of Ethereum | Sets, Groups and Fields | Lesson 1

Awesome. Very well. So, we can slowly get started. Welcome everyone. Uh seems like hope it's all working now.

And we got uh we got many people joining for the second phase of our study group. So, yeah, welcome everyone not just to this call but to the third week and the second part of our study group. The first two weeks were introductory and now we are diving deeper into the protocol. Uh today we are starting um a track on cryptography. We are going to have uh five lessons on math and cryptography behind Ethereum.

Uh to understand the cryptography really u it has certain um requirements of knowledge of math algebra and uh we shared some prayer reading here. Uh actually what Matan already wrote here. Let me share the the book here as well. This is the link to the reading material. So this course is composed based on the um matan's um uh uh teachings from from the past courses uh this whole book project.

So you can always find the resources and take your own pace when reading uh uh this book. Um and yeah it's my great pleasure to to welcome you here Matan our our teacher our professor here uh Matan is a PhD in mathematics studied in in Israel in Netherlands in Germany uh active in uh in multiple fields and a part of Ethereum foundations u the PSC team um also did the where he also did the whole course that I shared with you before guys but for us he prepared a special version where he condenses it into five sessions so it's going to be intense I hope you guys are ready to do some real math and uh um yeah uh Matan I mean the stage is yours it's uh it's uh your uh your class basically but if you guys need anything and if you have any questions we are still here for you so yeah thank you so much for joining us

uh thank you Mario for the the kind introduction and hello everyone uh so as Mario said uh I'm um I'm a mathematician by training. That's what I did my uh most of my adult life in academia. But um since a few years I'm out of academia and working in various places uh currently at Ethereum and one of the things I do is is try to to teach uh mathematics for cryptography for people without a formal background let's say apart from high school. Yeah. Sorry about that.

And um so so um as part of the the sessions that uh we plan with Mario h the idea is to give you a taste of um the mathematics that is relevant for cryptography. If you look at the book, you you see that the the book is much much longer than anything we we can hope to cover. But still um we can um we can sketch a few things. And uh apart from the mathematics of course we will discuss some cryptography that uh that is built on that uh mathematics. Um somehow my tablet is ah okay it's sharing.

Yeah. Yeah it's all here.

Um so so today I want to talk about um I hopefully two things uh groups and uh fields. Each one of these topics is in fact a a in the university you take it as a semester a a course for an entire semester one on groups and one on fields. So obviously we're covering a very a very uh surface level uh things. Um, nevertheless, I think it's it's actually a nice challenge for me to try to um find the the shortcut uh way of teaching you what what is really needed in cryptography and getting to um actual applications. Okay.

And um we had I asked Mario to to circulate um a prerequisites that is um I think chapter well chapter one or zero in the book uh which is sets and and functions. Um but let let me let me do a recollection. So a set is a collection of element and that um that is written with a curly brackets and each element I mean the elements are separated by a comma. So for example, you can write the set A as three elements 1, two, and three. And you see the curly brackets h in the uh the left and right hand sides and and comma separating elements.

Another way you can write a set is by let's say B is the set one 2 3 dot dot dot. So this dot dot dot really means that there is a rule that is um transparent from the first few elements and the set contains all the elements that satisfy the rule. So the this set of elements is the natural numbers. This is natural numbers. Um in fact usually it is denoted as this um this fancy n and another another way to to specify a set is again with this rule but instead of doing these three dots I can do um let's say B is the set of all X's such that X is a natural number um and X is bigger than five.

Okay, that's also a legitimate set. And this is this is a a convenient way to to do this is like the the the entry condition to the set. And and this this line is is all the all the elements satisfying the entry condition. Erh, one thing I forgot to say before I move on is that I I like questions. I I think uh generally questions are helpful both to you and to me and I I don't want to restrict the questions only to the end of the session.

So feel free to raise a hand and and ask uh whenever you want. Erh and with that with that said, uh we will also do I forgot to say but the plan for today and and for the other sessions is to do a 50 minutes um first part and then a 10 minutes break and then um an hour for the second part. Erh we will of course reserve some time uh for questions at the end but again uh feel free to uh to ask uh during the the sessions. Okay. So so if I can write a set like with with this entry condition then I can I can define the following set.

This is the empty set. It's the set of all x's such that x is not equal to x. Okay. So you see that this this kind of interface gives me flexibility to write a a pretty complex logical a logical entry conditions that define sets. Erh and of course the the empty set is uh is important for many uh for many uh kind of anchor applications.

Erh, one thing you can do with two sets is to take the cartisian product of of sets A and B is the set that is denoted A X or A * B and this is the set of all ordered pairs a comma b such that a is an element in a and b is an element in b. missing. M and so for example if h you take a to b a the interval one up to two. So this is on the line of numbers. This is the set of of all numbers between 1 and two.

And you can take B to be let's say the interval 3 4. This is a let's say this and then the the cartisian product of a and b will be a subset of a a of the the two-dimensional plane h that is depicted as follows. So let's say this is three and this is four and then you take the the square like so is in fact the cartisian product of a and b. Okay. And last but not least um from the recollection is what what is a function?

So a function f from a to b is a rule that assigns for every element a in a a unique B in B. H denoted F of A. And so you can think of a function as um like a computer program in in a typed language that is um this is the input. This is a a is the the type of the input. B is the type of the output.

And uh a function is like a function in in a type programming language that has the input type A and the output type B. So it is allow it needs to to give you a way um a way to associate a unique output for any input.

We have a question in the chat maten uh asking true random cannot be a function correct. Well, what is true random? Um, there is a a a section in the the first chapter of the book about um the counter counter theorem and one of the coreries is that true random cannot exist. So that that may be uh some answer. But again you can uh you can try to define true random in a different way and then the discussion becomes more involved.

Great. Thanks. Uh did that answer your question? Okay. So, so if um um if a function is like a program, we should also be able to compose.

So if a f if I I I forgot to say the notation for the function um right here in yellow you write f colon from a to b and of course it if I just change the the the output set b to some b prime then it's it's considered a different functions even though the the elements in B prime that do not exist in B may not may not be achieved by any input. So it's again it's a like in a typed language if you declare the function to be a to have an output type a b prime then it it is by definition it's different than a function with an output type uh b and so given two functions f from a to b and g from b to Then I can I can compose um g composed f is a function from a to c given by a a g composed f applied on an input a is g applied on f applied on an input A. Okay. So this is the reason for um the the order G and then F. Okay.

So so that's the preliminaries. Um and we we are set to talk about groups. So let's let's give the first definition. A group is a set G with binary operation. Let me call it for now star.

from the cartisian product of G with itself to G and that is you take two elements X and Y you apply this star and we will write X star Y for short uh in what follows Apart from the the binary operation, we require to have a a specified element E in G such that the following conditions hold. So the first condition is um let's call it unitary unitarity. This means that for any x in g x operation e is equal to x and it is also equal to e operation x. two is usually called associativity that for any X Y and Z in G if you do I mean we have a binary operation so you can only do X operation Y or Y operation uh zed or X operation Z and then do take the result and do operation with Z. But you can also a priori you can also do y operation zed and take the result and do operation with x.

And as the associivity axiom requires that these two two things are are equal. And what associivity gives you is it tells you that whenever you have a long string you know a1 operation a a2 operation a n you can write it in fact without brackets because a any bracketing of this of of any finite expression with the binary operation is is going to be the same by by the associivity axim. And the third axum is invertability. And he says that for any X in in G, there exist some element Y in G such that X operation Y is equal to E and is also equal to Y operation X. And uh we denote uh x x - one to be this uh this y.

Um so this is this is typically it's like um imagine that this this operation star with multiplication of numbers then uh then x to the minus one would be the the the inverse I mean would be the the the number such that x * x -1 uh gives you gives you one which is the the neutral element. this um this element by the way is called neutral. So this is it's neutral because because of the unitary aim right you you you do the operation of x with the neutral element you always get x. Okay. So this is this is a group and of course we want to have examples of so some famous groups.

Erh one is you take the integers this is denoted as zed and you take the binary operation to be plus and the the neutral element to be zero. This is a group h the inverse what is the inverse of of an element a in z the inverse is going to be minus a. So a minus one in this case is going to be minus a. Now if you want something with multiplication you can take the real numbers remove the zero element and take multiplication and the element one as the neutral element. This is another another group.

And this time if you have an element A, then A minus one is really just 1 / A. And and now let's let's take an example that comes a lot in cryptography. This is integers modul. So integers modul n is all the possible remainders of doing long division of an integer by n. What are all the possible remainders?

It's 0 up to n minus one. And I need to do a a I need to give you the binary operation. H. So the binary operation here is denoted modulu plus modulo n. Maybe we put it the mod mod n as a subscript and the neutral element is zero.

So what I what I mean here if if n is equal to 12 then this is a what you you you know as clock arithmetic that is if if now is if the time now is 11 and um I ask you what will be the time 2 hours from now then you do 11 + 2 that's 13 and then you do um you do long division by 12 and you take the remainder of what what you have left this is one. So so 2 hours from 11 is is one and that is exactly what what I mean by a plus modul. So 11 + 2 module 12 is 1. So 11 + 2 mod 12 is equal. we write it like this equal to one.

Okay. And and so I I still need we still need to verify that we have a a a the inverse for every element. But that's easy. If if you give me an element k then I also have the element n minus k and k + n minus k is equal to n. and n is equal to zero modu n.

So k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k minus one is n minus k. And and now the first fourth example something a bit more geometric. You take a a perfect triangle. you denote vertices by uh say 1 2 and three. And now you take o all the um all the symmetries.

So symmetries of um let's say t um you can regard the symmetries as as functions on vertices. that is um one symmetry is a is a reflection. So I take a reflection a reflections uh axis like so and that would mean that one two three is mapped to so one is not is not a affected by by the reflection along this axis. So one stays one but two becomes three and three becomes two. So this is this is one reflection.

This is one symmetry. You can do a two other symmetries in the two other um axis of symmetry. And you also have h rotations three rotations. So um say the rotation um like so. So this would be 1 2 3 goes to um 2 3 1.

Okay. So we have in fact three reflections and three rotations. And what is the e what is the binary operation? I mean the these are functions. So the binary operation is simply composition of functions or if you wish it's like a um you know you did one symmetry let's say you did a reflection and then you did another symmetry say a rotation you you simply do one and and follow follow it by the other.

And of course every element has an inverse because well for example the rotation I described has an inverse if you do the rotation in the other direction and the reflections also have a have inverse if you check it. So this becomes a group. Then the neutral element of course is the um is the the the operation that doesn't do anything to the vertices. So 1 2 3 stays 1 2 3 is usually called identity. So this is a a D3 the dihedral group and a a D3 has six elements.

Okay. So we now want to restrict. You see this example four tells you that groups can get Excuse me. Somebody has a mic. Uh, okay.

Sorry about that. You can go on.

So, this a a fourth example is is meant to show you that groups in general have a a a very Yes. The what was the question? Why D3 has six six elements? So, so how many reflections do I have? I remember it's like we only consider perfect symmetries of the of the the perfect triangle.

So the reflections you have to choose a an ax a reflection axis uh out of the the three options I I described here. um and rotations. You can either do the rotation I did one moves to two, two moves to three and three moves to uh one. This is a is you can you can uh regard it as the the trivial rotation. So it's like I don't do anything and I can do one goes to three and three goes to two and two goes to one.

Okay. So that that's the third rotation. So all in all I have three reflections and three rotations and that's uh six elements. But the point is you can read about about it in the Wikipedia or whatever. It's just to show you that the the structure of groups in general is can be very very complex.

Uh but we are going to make a a a simplifying assumption. A group is a billion Say a group G is a billion. If for any X and Y in G, X operation Y is equal to Y operation X. And a if you look at it, examples one up to three are a billion. But example four is not a billion.

And I I leave it as an exercise. you you find two elements X and Y in in D3 such that the they don't they don't commute. Okay. So henceforth all groups are a billion. Still there is a notational e discrepancy.

Um you can I mean I I I described the group um by G star E and uh let's say the inverse operation was minus one. Um but you could you could describe a group with the binary operation being plus and then it is most natural to call the the neutral element zero and the the inverse you you do minus the element right this is like like you know from numbers and on the other hand sometime I you may want to to write the group G with a multiplicative binary operation and then it's more natural to call the unit element the neutral element one and the inverse operation you you you keep as minus one and let's say both these these two notations are useful because sometimes as you saw in the example sometimes I the the the the structure I get from the group I mean I I get the group in in in a intuitively it's very easy to to think about it in in terms of addition and sometimes it's it's h more natural to think about it in terms of multiplication. So I can you know I can uh interchange uh these two notations. Now if G written multiplicatively is a group. A subset H inside G is a subgroup if uh the following conditions are satisfied.

One is that the the the neutral element 1 G belongs to H and two for any X Y in H X operation G with Y belongs to H. So that is this is a certain closeness of a the subset H. And the third aum is for any X in G sorry for any X in H. If you take the inverse of X with respect to the the binary operation of G then this inverse element still belongs to H. Okay.

So in other words, H with um the operation of G restricted to H is a group is a group in its own in its own right. So for example, you can take a um and I forgot to say the notation is age less equal than G. This is when H is a subgroup of G, we we denote it like so. And um classical examples I mean you take the integers this is a subgroup of the real numbers the real numbers if you take the real numbers with a with addition of course another example is you take integers modul 10 and you Take the subset 0 comma 5 then this subset is h is in fact a a subgroup. But if you take the subset 0 comma 4 this is not a subgroup of integers mod 10.

Why? Because if I do 4 + 4 using the operation in integers modu 10 my operation is plus modul 10. So since 4 + 4 is equal to 8 modulo 10 and 8 does not belong to 0a 4 okay so so I don't have a a the subset age is not closed under the the operation of the um of the ambient group integers modul. Um another non- example anti- example is a integers modul n is not a subgroup of the integers even though it is a subset. integers module n I remind you it's like the set zero up to n minus one and so obviously it's a subset it's a subset of of the integers but it is not a subgroup because the operation in integers modulu n is not in do is not the same as the operation in integers in integers I do simply addition and in integers modul I do addition modul it's it's it's completely different okay so um so don't be fooled by by there are many cases in which you have a subset of a group but this subset is not is not a subgroup because the operation on the subset is not the one coming from the ambient the ambient group that you started with.

So now the following theory if G a finite group is a finite group and H is a subgroup of G. Then the number of elements of H divides the number of elements in G. This is divides. Okay. This is lranch lranch theorem and you can see that in the example we gave 0 comma 5 is is a subgroup of size two and indeed two divides 10.

uh using lrange theorem you can you can start think about what are all the possible subgroups of a given finite group right because there are not many e divisors usually not many divisor of of small integers and that is computationally feasible many times to simply classify all the all the subgroups lrange theorem is is helpful in that regard. So as an exercise I propose size um write all subgroups of E integers modulo um modulo 20 Okay. Um, now uh there is a question in the chat asking how can there be an infinite group?

Uh yes. So infinite group the integers for example is an infinite group right? um infinite simply means that the number of elements in the the set of the group is not finite. So so yeah integers or you can take the integers cartisian product with the integers and then I saw also somebody asked what is divide. So this this is this is a a a positive this is a positive integer say n and this is another positive integer say k and we say that k divides n if I can write n as k * l for some l there exist some l such that k is l is equal to k * l any Other questions before I move on?

Feel free to ask folks to make sure you understand. It's uh it's no shame there questions or you can also raise your hand and otherwise we can continue. Yeah.

Yes. So, so the next thing and this is a central a central concept of groups that appear in cryptography is is the following. A finite group G let's say written multiplicatively is cyclic If um well let's say the number of elements in G I'm going to denote it by N and I I call such a group cyclic if there exist G in called a generator such that the entire set big G can be can be written as a G to the 0 is one G G² square up to g to the n minus one. Okay. So this it it sounds maybe surprising that there are such groups but in fact they they appear quite quite often and and in some sense they they are the building blocks of a finite ailion of finite ailion groups.

So in basically every finite abilion group can be a can can be described as the cartisian product of cyclic groups. Um but for now this is it looks special. Um um I I should warn you such G is not is not necessarily unique, right? So, so a group is cyclic if it has a generator, but it can have it can have more than one generator. Now, of course, I wrote the definition I in a multiplicative way.

If if G is written additively, Then a a G is cic. If um there exists some g in g such that a g is equal to zero which is g + g up to g + g + g and n minus one times and that's it. So this is this is I'm simply translating the the previous definition to the additive notation and the the H in both cases we write G triangular brackets small G. This means that that the group G is generator generated by the small element this uh by the element small G. Now examples of course you can take say a g is equal to integers modulus 6 and it is generated by the element one because you do 1 1 + 1 is 2 1 + 1 + 1 is 3 and so on.

you you get all the elements. But also this is slightly less obvious. Z mod 6 is generated by the element five. Why you take well I I I'll leave it leave it as an exercise. Um and um in general integers modul n is generated by k if and only if k has a um is what is called co-prime.

So it does not have any common any common divider to n. Now I don't have to have z mod 6. I can have z mod 3 times z mod 2. This is also cyclic. Um I I claim that this is generated by the element 1 + 1.

How come? Well, I write I write all the all the sums of 1 + 1 with itself. So 1 + 1 0 * well the zero sums with itself is is zero. And then 1 + 1 comma 1 1 comma 1 plus 1 comma 1. Remember in in the cartisian product of two groups the the binary operation is is is coordinate wise.

So the the binary operation in integers modulo 3 * integers modulo 2 is I mean if I do 1 + 1 1 comma 1 + 1 comma 1 I need to do in the first coordinate 1 + 1 modulo 3 so this is 2 and in the second coordinate I do 1 + 1 modulo 2 but that that's zero and then um so this This is two. This is 2 * 1 1 comma 1. And if you do the calculation of 3 * 1 comma 1, you get um you get 0 comma 1. 4 * 1a 1 is going to be 1 comma 0. and a a five * 1 comma 1 that is you you add 1 comma 1 to itself five times you get 2 comma 1 and you see we covered all the options this is this is six options h all generated by by sums of this element one comma one with itself.

So okay so we have uh some other possibilities of of cyclic groups and I guess we're almost in time for the break. So let me state the fundamental theorem for cyclic groups. So let let G written multiplicatively be a finite cyclic group. Then um one every Every subgroup age of G is cyclic and two if a the number of elements in G is N and and let's say G is generated by small G then G. So you take the the group generated by G to the N / K.

Well then for for any K that divides N. If you take all the powers of this element G small G the generator to the power of N / K. Um this is the unique cyclic subgroup of G of size K. Okay. So now you can you can use the fundamental theorem of cyclic groups to to classify all the subgroups of integers module n.

Okay. um using a generator using uh other means if you will and uh okay let me stop here but of course uh I'm happy to take questions before we take uh let's say a 10 minutes break

yes we had some questions first was about the exercise uh maybe if you can uh share a solution to that because wasn't sure how he can be sure that He wrote all the subgroups

h of what

uh that was uh uh even more up I think the exercise uh before

all the subgroups of integers modu

yes

well okay try in first of all you can you can find it in Google but you can try integers modulo 10 if you want that's you know you know by lranch theorem that the size of a subgroup has to divide the size of the group. You you only have two divisors here uh for 10. Um again, I I would recommend just, you know, Google it. I I'm not going to write things that can be easily found on the internet.

Yeah, that's that's fair. Um that's fair. Uh yeah, thank you so much. Um and there was a question about uh the uh current part about uh whether the definition allows to uh uh so so the groups can be uh defined multiplicatively or addatively but we can we would want to both add them and multiply right do the definitions we've seen allow for both at the same time

uh I don't understand the question uh I Feel free.

Sorry, I just I

uh raise your hand or maybe prefer your question and we will have a pause uh soon and you can maybe prepare questions during the the few minutes break. Um so groups can be defined multiplicatively or additively but we would want to both add and multiply. So it's not like we we would want to both multiply and add. It depends on the context. So a group is is like a collection of elements with a binary operation satisfying some conditions.

Now many times especially in cryptography this collection of elements is a collection of numbers. But numbers we can both multiply and and add. And sometimes the binary operation is going to to be some kind of addition. maybe addition modulu n and sometimes it would be some kind of multiplic multiplication like multiplication modulo n or multiplication h together with some other things but it can also be something completely it like it can be some some kind of weird formula that involves both addition and multiplication then maybe the the the better notation is to just do the binary operation write it as as this uh star asterisk that I said and this and regard it as as an abstract binary operation. It you know it eats two things and it it spits out a a a new uh what is restricted.

So when I said that a a subgroup this is I I I mean uh where did I define a subgroup? Yeah. So uh here restricted when I said a subgroup is is like a a group when this operation do g is restricted to e uh to h it means I mean you have a a binary operation that is a a a function from g * g to g this is g but h is a subgroup so h * H is also a sub H age h is a subset. So so H * H is also a subset of G. So you can take the function and and it's like a a define it on a smaller on a smaller input set.

This is h time h. This is restricted. So if you so age is a given that age is a is a subset. This age is a subgroup. If when you restrict the binary operation G to H.

So this is usually written do G in this line H * H and then then you get I mean up priority you get something to G but in fact a we we demand it to be a something in age and so this needs to be a group but maybe I shouldn't have complicated the definition in this way so you can you can just ignore this part. There is a perfectly good definition of what is a subgroup here. Um yeah. Okay. So let let's take a 10 minutes break now and of course you can write more questions uh meanwhile and uh we we resume.

Um so so let me so I don't see any questions but of course you can uh um ask later. Um the next thing I want to talk about is a very central notion in in mathematics in general but it's also important for us I mean and this is called isomorphisms. We saw that um well let's say integers modulo six is well it's a group of size six generated by one element and also So um integers modulo 3 cartisian product with integers modulo two is another cyclic group of size six generated by um by another element which in this case is different. It's one one comma one. And let me scroll back.

You see in integers modulo 3 times integers modulo two we can denote this this guy we can denote as zero this as one this is 1 + 1 so we denote it as two 3 4 and five. So under this change of notation we have um essentially integers modulus six. I mean if you look at the the the the binary operation can be defined by a finite table. You you put it's like a addition table, right? You put all the elements zero up to five in in a row and and in a column and you you you do them the addition table.

The addition table of integers modulo 6 will be identical to the addition table of integers modul 3 * integers modul 2 under this green h change of notation. And so we would like to say that these two two groups are in fact the same but they are not obviously they're not the same on the nose they like you know one has two coordinates and the other has the one coordinate. Um so we we want a notion that says that these two that that two groups are the same up to uh let's say a change of notation and this is isomorphism um but before so I need to say what is a um what does it mean to have a a um a a complete a um a change of notation. Um and this is the the following notion. a function um um of finite sets.

Let's say f from A to B is a bjection if two conditions are met. One is that for any two distinct elements A1 and A2 in A, F of A1 is different than F of A2. So it's like a f has no repetitions. And two, for any possible output B in the the output set big B, there exist an input A in A such that f of A is equal to B. By the way, this this condition one is called injective and condition two is called subjective.

So for example, if I give you a and b like so and I I I have it um I have the function described as the the arrows h here then this function is injective. This is injective. It satisfy condition one for any two elements a1 and a2 or a1 and a3 and so on the you apply the function and you get two distinct elements in b and subjective is um let's say I have two elements here I I may have three elements here then I can send the elements like so and and this is subjective and bjective. So you see injective in fact really implies that the size of the set A is has to be smaller or equal than the size of the set B. And subjective implies that the the size of the set of the set B has to be smaller or equal than the size of the the set A because subjective is like is like a covering and injective is like an embedding.

Okay. And bjective is both a subjective and injective. So it's both an embedding and a covering. It means this is a theorem but it's actually very easy. So let's say observation um the size of a is equal to the size of b if and only if there exist a bjective map bjective function f from a to b or f from b to a doesn't matter.

Okay. So that's that's a a that's what we mean by a a a let's say a onetoone correspondence, a change of names that does not does not omit any any of the names in the the domain set and does not omit any of the names in the in the uh in the range set. So now what do we do for groups? So let's say G is is a group written multiplicatively and H another one. Um, an isomorphism from a g to h is a bjective function.

f from g to h such that the following conditions are met. One is that f takes the neutral element in G to the neutral element in H. Two for any two elements in G. If you take if you apply F on the multiplication of X and Y in G, then it's the same as applying f on x applying f on y and taking the multiplication in h and three. This in fact this follows from the the previous two uh for any x in g.

Um if you apply f on the inverse of x then you get the same as applying f on x and taking inverse in the group g. Now so so this is an isomorphism and what what is happening here? Let's say G is a is is three elements A1 A2 A3 one of them is the the unit element but I don't care and write H to be f of A1 F of A2 2 and f of a three. Why can I do it? Well, um since since there is an isomorphism from G to H, then the number of elements in G and in H as sets has to be the same.

And since f is injective, if I apply f on on a1, a2 and a3, I get three different things. And since age only has three things, I I get all the things in age. So this this thing here is a if you will some particular enumeration of the elements in age. Okay. And now I write the multiplication table of um of G.

Say A1 A2 A3 A1 A. Here I have A1 A1 A1 A2 A1 A3 A2 A1 A2 A2 A2 A3 U A A3 A1 A3 A2 A3 A3 Now I do the same But for the multiplication table of h using this particular enumeration that I chose. So I have um f of a1 f of a2 f of a3 f of a1 a2 f of a3 and multiplication in h. So here I have f of a1 times f of a1 and here well I I'm not going to write all of that but let's say here is going to be f of a2 times f of a3. Now look at what what is going on.

F is an isomorphism. So I I go back to the definition. I see that condition two says that if I apply f on multiplication of two elements, it's like applying f on each of the elements separately and taking multiplication in in h. So what I have here is in fact by condition two is equal to f of a2 time a3 and this again by condition two is f of a1 * a1 so you see what I have here is this element a1 * f a1 was simply mapped to f of a1 * a1 this is the the first element element in the the the multiplication table of H and this was mapped to this element. So you see I I um using this enumeration f is is simply a a complete identification of the two multiplication tables of f of of of g and of h.

So in fact g and h are the same up to a change of notation. What is the change of notation? Just apply f on the elements uh of g. In other words, in a computer representation of G or or H, the computer doesn't care. H and G are the same.

And and that is um that is the example we had of integers modulu 6 and integers modulu 3 times integers modulo 2. It's these two two groups are isomorphic and so from a computer point of view it's the same. So, eg the notation by the way is Z mod 6 isomorphism is like equality with a with a tilda over it. So, Z mode Z mode 6 is isomorphic to Z mode 3 time Z mode 2. Mark and not every so we are we are dealing with a stuff that are need to be also computationally feasible.

Sometimes you know that two groups are isomorphic but it's not easy to find the isomorphism. It's in fact in in some cases it is considered computationally invisible to to find a certain isomorphism between two groups. Um so not always computationally feasible. Okay. So now that we have this notion of isomorphism.

Here's a theory. If G is a finite cyclic group, G is isomorphic to integers module N where of course A N is simply the number of elements in G. Okay. Um, by the way, how do you define this? So the this this is very easy to prove.

Let's say you have G uh written additively and you know that G is is cyclic. So it is generated by some guy G. You simply define a function f from g to um to z mod n by saying that g goes to 1 and of course g + g would go to two and so on. So you see so in fact up to isomorphism all finite cyclic groups are um are isomorphic to some integers modul. This is this is the importance of a of integers modulu n.

But as I said earlier it is not always computationally feasible to to find such an isomorphism and And now we arrive for the the main theorem in a in the theory of finite ailion groups. This is a structure theorem for finite aidian groups. If G is finite a billion, then there exist um positive integers n1 up to n k such that g is isomorphic to integers modulu n1 times names integers module nk. Okay. So, so this concludes the a the very the very short miniourse on groups that I h that I wanted to to talk about.

Um any questions before we move on to to fields? How to prove what the structure theorem are? the structure theorem this this appears in the notes but this is it's not it's not something I can answer easily h I mean it it it takes some time so if you want the the full pro the book the book I wrote contains full proofs for 95% of the uh the things on on up to elliptic curves and pairings if you have the patience I recommend but I cannot really answer and we cannot really cover it in these sessions. What or why must be a billion groups? What is the questions?

What is the question here? It's

Yes, go ahead. Uh yeah, in the the final theorem uh we have like uh we define this uh ser theorem uh for a billion group. So I'm wondering if that's also could be extended to other type of groups or it's only uh applies to a billion group. So so this is only applicable for a billion groups. However the and and as I said the proof of this appears in in the book I wrote but of course it's not it's not my proof it's well known.

So in you know in a few in in in a few pages of a of of the book you can uh you can find all the details. If you want a structure theorem for all finite groups not necessarily a billion this is a much much more complicated question but it was answered. This was a huge project of mathematicians in the the second half of the 20th century and the classification it it is a theorem if you will that that takes 10 about 10,000 pages. So you see the complicate the when you move from from a billion a billion to none a billion the mathematics become much much more complicated. There is still a there is still a classification theorem but it's very very hard.

So we we take a huge simplification here. Yes. Okay. So, we have uh 17 more minutes and um in this time I I would like to start talking about fields. Um we will continue next time.

So if you looked at the titles of the sessions uh the next the next session should be on fast for year transform. um what I plan to do the the the titles are kind of tentative because it's not clear. It wasn't clear to me how much I would uh be able to cover in the given time frame. But I think what we'll do is we'll talk about fields today. We'll talk about fields next time as well.

And uh we're we'll probably next time we'll start talking about uh um fastfor transform which is a very good in my opinion a very good application of um the stuff we talked about in in uh in the groups and fields uh session. So what is a field? A field is a set f with two binary operations. Um usually one denotes them as as plus and multiplication. um together with the two elements.

These are like a special elements 0 F and a 1 F uh satisfying the following aims. One is that both f with plus and zero and f when you remove zero and you take the multiplication and the element one are a billion groups. and two for any x y and zed in f x * y + z is equal to x * y + Um so you see what does it mean that um f with plus and zero is an a billion group. It means that um for any element x in f I have an element minus x such that x + - x is zero. And what does it mean that f removed when you remove zero with multiplication n1 is an a billion group?

It means well I mean of course a billion means that the plus and the multiplication operation are commutative but it also means that um for any x in f there is an element x - one such that if you multiply x with x - one you get one. Okay. So these are two a two operations both of them need to be um need to satisfy the axioms of obedient group separately. So also associivity right if you do x * y * z like this it needs to be equal to x y z like this. And the same for for the the the plus x + y + z needs to be equal to x + y + zed with these brackets.

Okay. And so on. Zero needs to be the neutral element with respect to addition. One the neutral element with respect to multiplication. Um and so this is a a spelling out what a axiom one means.

Axum 2 is about a the compatibility of addition with multiplication. This is called distributivity. Okay. So what are famous fields? One is the real numbers.

The real numbers with addition multiplication 0 one two the complex numbers three what is called the rational numbers. This is the set of all quotients a over b such that a and b are integers and b is non zero. observe um if if I have a field and I have two elements in the field such that x * y is equal to zero then we must have x =0 or y equal to z or both and the reason is that well if x if x * y is equal to zero then I can multiply by x and x is not zero I mean if by by towards contradiction x is not zero then I can then I can multiply I mean there is x uh x -1 and I can multiply this equation by x - one I at x -1 * x * y = to 0 * x -1 and that's the same as saying y because x -1 * x is 1. y is equal to zero. So if x is not zero, I automatically get that y is equal to zero and vice versa.

Um so now consider integers modul n with addition modulo n multiplication modul n uh and zero and one and the question is is this a field? So theorem ZN is a field if and only if N= P is a prime. is prime and how do we how do we see this? So look the the associivity and um inverse with respect to addition and I mean all the axioms are pretty obvious. The only thing that is not obvious is a multiplicative inverse.

So only thing in doubt is a multiplicative inverse. What does it mean multiplicative inverse? I give you a number between zero and n minus one and you need to find a number such that if I multiply my original number with this new number and I do modul n I get one uh is is this inverse or I mean does this multiplicative inverse exist for all nonzero elements in z modu So if n is not prime, let's say n is equal to k * l with um k and l smaller than n smaller than n and bigger or equal to one. In fact, bigger than one. So this is not prime.

Then K and L are zero divisor are M I mean K * L is equal K and L are elements in integers modul N and K * L is equal to N which is equal to zero modul And this is a contradiction because in a field remember the observation in a field we if x * y is equal to zero then either x is equal to z or y is equal to zero and here we have that k and l are non zero. So if n is not prime any decomposition of l as a product of two numbers shows that z mod n cannot be a field. Now if the conversely if n equals to p is prime then I take now I want to show that there is a multiplicative inverse so I take any nonzero number k in integers modulo p this is integers modulo n when I remove zero H because P is prime the GCD the greatest common divisor of K and P is equal to one. I mean they they they have no no number that divides both of them. K is is smaller than P and P is prime.

So they they can have no common integer that divides both of them by the extended uh ukidian algorithm. This is in the book. Um there exist U and V some integers such that K U plus P V is equal to 1 i.e K * U is equal to 1 modul P because if I do modul P I I remove this PV. So k inverse can be taken as u u I mean u modul p is going to be k inverse.

Okay and hence z modul p is a field. I mean you can check the other the other axioms are they are very easy to check associivity invert the only the only non-trivial axum to check is invertability with respect to multiplication this is h this is what the proof covers. So a a denotation FP is a a is this is integers modul with addition modul multiplication modul uh zero and one. This is the field a prime field. Okay, let me stop here and uh we can take a few more questions before we end.

Uh yeah. Well, cryptography experts uh feel free to uh to push it further. Uh you you are welcome to ask here an abstract question. What is the connection or relationship between polomials and sets in ZK proofs? Um I I I'm not sure what you mean because uh um set as as I uh as I talked about a set is anything is a set you know also a function is a set you is is going to be a subset of some cartigian product so I'm not sure what but polomial We will talk next time we will definitely talk about polomials.

These are very central objects and they appear everywhere. It's not just about ZK proofs and maybe one of the messages of of these lectures is I mean sure it's it's good to to learn about ZK proofs but the mathematics apply to a much wider set of