ProgCrypto (ZK) Study Group 2025 — The Moonmath Manual to ZK-Snarks: Chapter 4 Algebra

Okay, great. So, as usual, um we'll we'll do the same thing as usual. We'll go through each each section and uh after going through each section, I'll probably go through some examples and um I will be open for uh anything, right? Um, stop me at any time, you know, open your mic. Stop me at any time when you um want to ask questions when you have spec specific things you are not um you don't really understand yet.

Um and we can discuss, right? We can talk about it and all you know. Yep. So that's that. Let's begin.

So okay, chapter four. So this is what we're going to cover um this week. Um okay, let's start from 4.1 commutative groups. Any anyone have any problems with this section?

Want to go faster? So, um, finite groups. Nope. Generators. Nope.

Wait, let let me turn on my uh message just so I can see if there's anyone in the chat as well. Um, okay, great. So fin groups generators exponential map any questions factor groups. No pairings. Wow.

Okay. Oh, exponential map. Okay. Uh okay. Um so great.

Um what um what questions do you have on on the exponential map? Um, if you don't mind sharing Okay. Um, okay. Then let's look at X1 map and and see if it helps, right? Okay.

So um first of all um to add some context I might as well since we are here I'm going to go through a little bit on groups finite groups and all that. So um groups um think about it as a set right it's a set with some operations. So um that's why you can see um of course it has some property like commutative associty but what it means is essentially you can do um it follows the rule of um arithmetic um sum of the rule of arithmetic like um addition you know a plus b is equals to b plus a it's similar to that so yeah um there is a neutral element which is the identity usually so one or zero depending on if it's a multiplicative group or a additive group um and yeah there's an inverse All right. And inverse in this case negative one for an additive group and uh you know uh power of negative one for a multiplicative group right so that's this existent. Usually when we talk about groups we do talk about communicative groups and we sum one all these properties in there in there and um groups usually yeah we represent it like this right um if it's additive is this if it's multiplicative it's um here okay and the difference is essentially the operation so we define group as a set with some operation with one operation right usually one operation um so um in this case it's G and addition in in this case uh It's G and multiplication, right?

And yeah, that's what a group is. Finite groups, finite amount of things, right? Infinite group can be integer with addition, right? Because we can have integer that adds up to an infinite finite group. Um, usually we'll work with some um finite amount of number.

So Z6 here is just natural number up to six. So 1 2 3 4 5 six. Essentially a set that contains these six numbers so to say. Yeah. And uh yeah that's that's essentially yeah can be committed about six you're right yes so that's essentially what finite groups are and generators are just a value or element in in the in such groups um that you can use to generate other elements.

Um, we usually will be more interested in groups that have a element that can generate every other single element. Um, so that that's pretty interesting. That's the interesting thing that you usually look for, right? With one one generator that generates every other element in the group. Um, yeah, but again, you can a group can have multiple generators.

Um, no, generator doesn't need to be a prime. Uh in fact um even in non-prime sets so non-prime groups um you can have generators as well uh it doesn't need to be a prime um it's just that um how do I this is just that sometimes some generator um I I believe we do use prime generators in in some cases but generally what we want is one a generator that gives us certain properties. Um that's why in practical applications like um in um for example our famous um CP256K1 uh we choose a specific generator point right and then we use that point to generate the rest of essentially the the field um yeah that we use um but no it doesn't need to be private number um generators that is um Yeah, but we do um choose a we do like uh gen like groups that have a generator um that generates all other elements in the group. Yes. Um ZK, you're right.

Um some elements are able to generate all the other elements in the group but not all, right? Some generator only generate three or four, right? Um a very good example is um in in the group of um in an additive group of let's say integer. Um technically speaking, two is a generator. You can generate every other not every other number you can generate a lot of numbers that can generate 2 4 6 8 you know and so on but it's not the generator generates all the other elements in the group right um I would say one is probably in this case the generator that's able to generate all other elements in an integer or I would say natural number um you know integer yeah in natural number I'm not sure wait natural number yeah generate all the other natural number because you can just one plus one 1 plus then if you continue plus one.

In this case, you are able to generate every single number in the uh natural number group. So yeah. Yeah, that's that's what generator is. Um generator doesn't need to be prime number in this case. Um it generator is just a number that you can use to generate other numbers.

Um yeah, great. So um yeah, that's that. So let's go into the question. So exponential map um so exponential map here sure um is just that it's essentially a mapping that maps um a group um in this case they're using editive group so an editive group um to another group in this case um so here we are basically saying hey um so let's Take the example here is ZN class. So this is an identity group of integer um that is of size order n so size of n um and yeah we want to map this to another group and we want to make sure this mapping is one to one right so um exponential map because it it operates as in exponential of gx.

Um so this G is is not a predefined in this case it's like basically we want some mapping in this case this is the mapping and we want to map values in ZN to another group right it essentially creates a new group um so yeah um and when we do this we want this to have one to one correspondence meaning that um we don't want values from um ZN when we do this mapping to um two values to map to a single um non-unique value. Right? So we want every mapping to be unique. So that that's essentially what the explanation map is. Um to put it very simply, um I'm going to go through here.

So to put it very very simply, um this this is an example. Okay, we'll use this example. Um so this is discrete log to the base of three and this is the map, right? So um wait this one let me see oh results four um this is not a good example wait let's take this yeah this so this essentially says um we take this map of um this additive I believe yeah um this additive um group um that maps to this multiplicative of order five. This is order four.

Um and this is the mapping right 3 to the^ x. And one thing that we need to um essentially um be aware of is we want it to respect um essentially the the law for for each group. So what what do I mean law? Basically the operations, right? uh group of five doesn't contain zero.

Uh yes, a multi group of five doesn't contain. So you're right. Um this is because um actually in all multiplicative group um so zero it's interesting in that um sometimes you you can't well we don't necessarily generate zero out of um this mapping um it's more towards so zero in in some definition we'll say like let's say additive root right we want a because remember this actually it's because of this uh definition here um existence of a neutral element so the set that you are defining sometimes we'll say like hey you know we we specifically define this set and then we'll say hey there is a identity or there there's a neutral element and this element uh is zero uh in the sense that any value plus this value is is equals to zero or and so on right uh like the inverse this value times this value is zero. It's like some neutral element, right? And yeah, that sometimes we define it but sometimes you can't really at least from my understanding it doesn't necessarily mean that it's it exists naturally in in the set.

You can define a value such that you you define basically hey this is the neutral element and and we we do this right um but you need to respect of course that element times you you get the inverse multiply the inverse by itself and you should get that neutral element uh in additive very very commonly it will be zero in multiplicative very commonly that will be one so multiplicative group sometimes it doesn't I mean it doesn't necessarily have zero the zero of a multi-deree group usually we define it as one. Um it depends on how the group is defined. Yes. Um I'm not sure if I make sense. Uh I might not be describing this very accurately.

Anyways, yeah. Um so let's let's get to here. Uh where is where were I? Um okay. So in this case um so this example um this essentially okay this essentially is um calculating for the mapping from X.

So like let's say I think this given this X is um let's show generator three. So this is a generator and you basically do this computation here and you get four right and this value excuse me um this value should respect the like it should respect the law also in in this right basically um anything you perform in act like in Z4 um when after you map after you do this exponential map um the values here or more like how do I put this h. So 1 + 3 + 2 in in this group for example 1 plus 3 + 2 is equals to 4 5 6 which goes back to um two I believe in this I believe. Yes. And in this specific case two here if you map to Z5 should always be four essentially right.

Um yeah so let's read this a little bit. Uh so in in this we perform this in a remainder class group here and then apply this map. But we can technically do the same thing in this group and then it will result in essentially the same value. Basically your competition works um your computation should translate well like you should respect what will happen in in the group that it's coming from. So any computation performed in Z4 when mapping to this should be the same as if you perform a computation here in Z5 multiplying the growth of C5.

Um yeah that's that's essentially what an exponential map is but specifically we are talking about um exponential um so like g to the^ of x Z4 and Z5. I also don't think they have the same generator. Yes, I believe. So, yeah. Uh Gerald, does that like answer your your question in this case?

Nice. Great. I think there's one more question somewhere. Uh in explanation, how active group order for maps to multiply group of group order five? Oh yeah, I think that's that's answered by um NH base GD script.

Are you talking about uh BG discrete block? Wait a G. Oh uh since exponential one respect the group can show that this map has an inverse respect base. Uh ah this one okay wait 4.1 what is it talking about 4.

1 ah so um this is um essentially bas discrete log is is this right um this is the reverse so this so if there is a one to one corresp correspondence uh if this is a one like if there's a one to one correspondence of Z to G ZN to G in this case right if this is true can say that if this is true the reverse the inverse of it um is true as well so this is essentially a reverse right um uh can we put the set damn I I don't I need to install something else. So this is essentially inverse of this right uh so that that's it that's what it is. So log gx um essentially just shows a mapping from g to zn instead of um the previous where it shows zn to g um where z the mapping of gn to z is um in this case um g to the^ of x right and g is a generator um so for example the inverse of this would be yes it's hard to generate x from uh from result discrete lock. Um, at least that's what it wants to do. Um, and and it's the thing that we rely on to make sure our cryptography is still relatively safe.

Um, yeah, that's the yeah, script lock. But yeah, for for example, this um the so in this case, let me see if I can uh get the pen. So in this case the the inverse should be um Z uh go Z5 mapping to Z4. Sorry my my handwriting is crap. Um and then and this will be base three.

So log three X. Yeah. So this would be its inverse, right? This is the inverse. Okay, great.

Uh any more questions before we move on two to four in example 4.3 4.4 4.3 4. Oh, this two to four.

Ah, yeah. I mean, if you don't know two, um, it's harder to know it's it's four in in in here, right? Um, yeah. Or I mean, from four, you can't really know what's two. Yeah.

In the opposite way. I will assume there's no questions. So let's move on to oh there you go. So it's a mapping because it's both injective subjective when A is not equals to B F A is not equals to FB. Uh and for every B there is an A that maps to it.

Yes, you can confirm this by checking by hand. Uh, yep. Yep. Bing, Bing. Yeah, Bing, you're right.

Um, thank you for the additional um context. This helps a lot. By the way guys, remember there's a chat. You can look at the chat. There's a lot of discussion going on there.

So do take a look at it um while I'm also talking. Um you can also talk by the way. But yeah, thanks Ming for the for the more accurate uh explanation I would say. Yep. Great.

Let's uh continue. So uh factor group any questions on this section? Okay, let's go into pairings. Any questions on pairings? Oh, okay.

Um, great. Uh, wait, this is under pairings, right? Oh, this after parents. Okay. Any question on cryptographic groups.

So in cryptographic groups we talk about um DLPs and a few things that that uh modern cryptography rely on and some assumptions um to make sure that things are essentially safe. Um we also talk about here so here we actually talk about h= g to x. Yeah it's essentially given this um it's pretty hard to find h without knowing x. Um, essentially finding the inverse is hard. Um, that's that's what uh the yogi is to be very I mean I'm being very a I'm being I'm explaining this in a very simple way.

So it's yeah um okay I I see a question. What is non- degenerates and pairing? Uh pairings non degenerates. Okay. So um essentially so um let's talk about pairing a little bit.

So pairings um or pairing map essentially um it's so a pairing map is this function. of G1* G2 maps to a group tree, right? Group uh one group um maps to another group, sorry, one group operates with another group and then maps to uh group three, right? In this case um so and pairing map. So it maps it and it makes that property called bilinearity holds.

Um which means that essentially if you do uh this okay this identity okay so g1 um time g times g1 prime and g2 so this pairing check it's equivalent to this right so it's equivalent to operating okay to put it very simply um doing this operation or doing this operation is equivalent to doing or doing the calculation in these two groups is equivalent to doing the operation or the calculation computation in G3 um which is the result of this function right um this mapping so to say so um yeah this this is explaining a little bit better here so bum means that it doesn't really matter if you execute the group law or once they appear the biomat or we first apply the map and then apply the group law um group law here is the operation itself. So the operation um it like addition multiplication it depends right it depends how you define the operation um as per groups right in a group um but yeah uh usually multiplication addition um yeah that's that's what it is so it doesn't matter if you do it the calculation here first or you do the calculation here this should map to this um and um let's now talk about nondeneration so non degeneration means that u okay Remember in groups when we talk about a neutral element it's very likely the identity the identity element I guess um so essentially a neutral element for a additive group is um for example um a neutral element for additive group will be zero. A neutral element for for a multiplicative group is very usually one. um neutral element here just means that hey you know if it's a additive group um 0 plus whatever it's equals to that value. So 0 + 5 is 5 and for multiplicative proof is 1.

So it's 5 * 1 will always equals 5. 6 * 1= 6 and so on. Right? So non-direct just means that if if the result in G3 or result of the mapping is a neutral element let's say if it's one or zero um in this like incept yeah if one or zero right then one of the input value in G1 or G2 must be that neutral element and yeah so I think we can look at example here the most basic example in involves this and present uh addition. So this essentially is um so the this mapping is um a * b on integer um and so this is non degenerate because um given let's say okay equation a + b time c so to say this holds this is barity and then it's going to generate because let's say this is zero then it means a or b must be zero in this case.

Right? Um if a * b is not it's zero but a and a or b is sorry if a * b is zero and a or b is not zero. um then it's not non degenerate and it also imply I think there's some problem with my sorry give me a moment okay does also imply that um there is a well I guess in this case there is a um inverse of a value not inverse actually. Yeah, I guess. Yeah.

So I guess so. So there's an inverse of a value in in the in G2, right? Um yeah. So yeah, this this is what generally non degenerate just mean that hey you know given given some given that the pairing result pairing is zero some one of the values should be zero. um if it's not then um it's not on and that's calculating it when you calculate things here it it might not necessarily map to the correct value here.

So unless a or b is a natural pairing result should not be a neutral element. Yes. Um a unless one of them is a neutral element. Uh yes, but this is the this is the nondenerate um property, right? You can have a pairing map that is degenerate.

Okay, that's a little bit. Okay, anyways. Um yeah, there's a you can have a paring man that is degenerate. Um but this is a nice property to have um I believe. Yep.

Great. So let's uh continue. Any questions? Just just show it out. We we can go back to it anyways.

Yep. So group um my sources are already here. Let's let's talk a little bit about this. Yeah. So here the result I'm not the result can be unique and not accidentally equal to neutral element and thus making false validation.

Um I am not Yeah. I mean I'm not exactly sure if that statement is right. The result can be unique and not accidentally equal neutral element and thus meeting false valuation. So yeah I'm not exactly sure about this. So if if anyone of you have have any insights in this yeah do participate but yeah I am not sure it exactly means that but on the yeah not being the check pairing of results C should be C and not E.

Yeah, I mean in that case I suppose so. So it's it's a unique result but I'm not so what I'm not sure about if I'm not that what I'm not sure about it's essentially um yes you are right in that but I'm not sure if that's the only reason why non-eneracy is is a good thing. Um, yeah. I am. So, what I'm not sure about if if that's the exact um, so that's I don't I'm not sure if that's the the only reason why non degeneracy is is a good property to have.

Um, but yeah, I mean, you might be right here. This why I'm not very sure. Yes. Okay. So uh cryptographic groups um here here we are talking about groups that we're usually losing in cryptography essentially but yeah um they talk about discrete problem discret problem um yeah so let G be a cycle group of ordered R and G be a generative of G we know that's an exponential map that maps residual classes from module RF arithmetic onto group one to one and script rock problem is t of finding an inverse to this app um yeah to find solution X R to equation for given HG which is an element from a group.

So yeah um there are groups in which this is assumed to be invisible meaning it will take more than the time in the atoms of the universe some of them um to solve and there are groups in which isn't so we are interested in the secure groups um yeah so in public cryptography this is um quite a common thing um encryption I believe just um symmetric is asymmetric encryption I mean but I think both does use this but yeah um it's used in normal encryption decryption as well um so yeah here in this case secret so this is quite common um need to find the result for this equation and it's pretty hard to find it Yep. So there's also the decisional def assumption. Um so this is definition. So let G be a finite cyclic group of order N and let G be generative G. The decisional DDH problem is to distinguish G A GB GA from the triple G A B C for uniformly random values ABC that is an element of the integer of all integer set of order R.

Um, yep. So, these are all things that ensure our cryptography protocol remains secure. Um, there's also this um, def helmet assumption or competition def. Yeah. So, I'm not going to uh what's it called?

Read this out. But yeah, any questions? What's the difference between decisional and computational DH? Very good questions. Okay.

So, let's let's look at uh so let's look at the definition. So, this is um problem is distinguish this from the triple this. And if you look at here this given a randomly chosen AB of this it's not possible to compute GAB if only G ga and GB but not A and B are known um it's slightly different in that how do I this okay from my understanding Okay, given this. So given this and some random value ABC without um this is triple, right? Wait, let me let me think for a little bit.

Just look at my notes. So, so DDH is stronger than is stronger assumption than uh CDH actually. Um so so it's actually a stronger assumption than uh so DDH has actually assumption C CDH and the difference is essentially um given this determining if so determining if C so so this C is necessarily equals to A * B um is hard or more like if you want to look at like let's say GC um you want to determine if GC is equals to G to the^ A * B um it should be hard for you to do so in this case um yeah but yeah So however, so if you look at pairings, so at least groups that you can efficiently compute pairings, you realize that pairings are not DDH. is secure in the sense that given some GAB you can check if GAB is equals to GC in this case by doing a pairing check because of yeah by linear property implying this um yeah so Technically, at least from my understanding, um, in pairing friendly curve or like pairing friendly curves are are not really DDH secure. However, I believe they are CDH secure um in the sense that computing.

So here is essentially okay uh let me let me see what I can okay so essentially so this you you can compute this right um but computing GAB so you can check the pair you can definitely check pairings of Um you can definitely check pairings between um of of to to do check to actually get um get the relationship of um GA GP and and some value Z which might be GA B right but in this case although yes you can but in here it 's considered acceptable um with CDH assumption. So, is it correct that DDH is checked? Yes. No. And DH is a search problem.

Knowing JB, compute GA. Uh he has such problem. Let me think about that question. Is it correct that DDH is checked as long as DH is a search follow GV compute GA? No, you can compute GAP in in this case.

Wait, no, you cannot Yeah. Is it I'm not sure if I would call it a search problem but yes uh given JGB computer JB is hard in CDH assumption. comparing to pairing groups is nearly because check the we want to be hot in DH. Yep. So, yep.

ZK is giving uh ZK, I think, and also um MHA is also giving really good feedback in the chat. So, yeah. Uh pairing groups, it's DDH invisible because pairing can help check the comparison where we want it to be hard in DDH. So well in I guess in CDH we it's not this hard of assumption. So uh in this case we gave an example for example we want Z = G to the^ A but we don't want people to know Z equals G to power AB.

So in this case you can find that out via a pairing chat.

Can I add something here?

Sure. Go ahead. So I think the question on computational and the question on search problem and whether it's uh check yes or no I think that's somewhat accurate I think uh because okay it's on your screen right now like if you read the paragraph to see why the description is necessary blah blah blah.

Mhm. um at the end of that paragraph sorry it's the paragraph below so given

oh okay

a g g to the^ of ab you can decide if

the dt dth uh assumption holds but then it's hard to compute g to the ab

mhm

and then in this case the weaker assumption means that it is better because there's less assumptions. It is okay

or rather stronger.

Yeah, strong you mean stronger than the um what's it called? the L.

Yeah. Then the decisional one because the decisional uh problem you're just checking, right? You're checking if some Z equals to G to the A.

Yes.

But then the combinational problem is trying to ask you to compute G to the A. Oh,

I see. Thank you very much for the context. It helps. Okay. Um I guess any any more questions from the audience or any more context that you would like to add to this and I'll continue I suppose again thank you very much for adding to this um yeah it helps me as well okay so next hashing to groups anyone have any questions regarding this Hashing to Oops.

Questions. Hash functions. Hashing to cyclic groups. Peterson doesn't hashes pseudo random function families in the H secure groups. Okay, then we move on to commutative rings.

Okay. Hashing into modular arithmetic. anyone actually tried this in Sage? Maybe we can we can try later together on like my laptop. Um yeah.

Okay. I think there's still conversation on DDH. Uh this means that there are group DH or DH there cannot be groups in which DDH holds but CDH doesn't hold essentially. Yes. CDH is um better than DD in strength.

Yeah. Um I guess the so in in the book okay um let's let's go back to the sitation. So um ZK ZK was talking about I think DDH is kind of depending on CDH2 does that statement like pairings one um so and then being replying this means that there are groups where CDH holds and DDH does not hold well they cannot be groups in which DDH H holds but CDH does not hold essentially yes CDH is uh better than DDH in terms of strength but I found this sentence really phrase the book yeah I think the book the book talks about um the CDH assumption being weaker than DDH. Um I guess that that's why it feels weird. Um in that sense I guess they they are talking about it's a weird it's a weaker assumption but not necessarily a assumption in that it accepts more.

I think that's that's the reason why they say it's weaker. Um not not exactly that that yeah I think that's that's why the book phrase it like that. Um so it's weaker in the sense that DDH accepts less like the DDH assumption accepts less like there are higher yeah I I think not higher they are DDH is more strict than CDH in that sense it's weaker in the assumption front not in the I yeah not in the I mean I don't know how to put It's talking about the assumption strength not the not the strength of Yeah. Because DDH DDH if DDH holds CDH must hold but if CDH holds DDH does not necessarily hold. Yeah.

The reduction could be could be if we break CD we can comput J if we and compare Z because J CH isn't it okay? Yes I think I think Ch is right. Um, if we break CDH, we can technically break DDH. Um, because we can find GZ equals G to 12 A to check G to A B= G to A plus and G to B in pairing it has to be easily compute G from G to GB. Yes, that's right.

What? Oh, because assumption is similar. Yes. Uh, break harder problems, you can break the easy problem. reason assumption.

Yes, you're right. So if you assume if you basically use the because problem Yes, you're you're right, Bing. In that sense, yes. Thank you, Bing. Great.

I'm so happy there's so many discussion here. Okay, great. Okay, let's get to Rafina. Uh what does non-unit mean in example 55 vers 55 unique? Oh god.

Yeah, the search is not great. Um 55 page 54. Uh wait 55 page 54. Let's get here. Sorry.

Moment 54. Example 55. Uh where is Oh. Uh, honestly, I do not know this. This I actually don't know.

I think this is a printing error, but I might be very wrong about this. But yeah, I I have a feeling this is a printing error because I think I saw similar things up um in pairings as well. I think this is marked for removal or it's basically saying that the the example is not unique. I I'm not very sure. Um yeah, correct me if I'm wrong.

Yeah, I'm not quite sure why this is written non-unique. Sorry. Yeah. Okay. Um yeah, hashing into sorry hashing into um commentary rings.

Any questions on commutative rings? Well, this is like a bunch of symbols. Um, okay. Hashing into moderate arithmetic. Any questions?

Slowly down. Try an improvement method. Anyone try to implement this? Actually, it's fine. Um, let's continue.

Okay, fields. Um, any questions about fields? We usually so um one note here. So, we usually actually use prime fields um in most of the cases um in cryptography at least. due to the fact that there are quite a lot of um well not quite a lot there they are interest there are properties that that we want in in in prime fields or in prime yeah fields with prime order um that's why prime fields are quite commonly used um yep so let's Continue, square roots or fields.

Any questions? Yeah, do do just put in the chat or stop me when you have questions or you want to discuss about something. Hashing into prime fields. Uh this is the same as um hashing into groups. Actually actually most hashing into prime fields has to do model arithmetic and hashing to groups.

Um they they all use the same mechanism and hashing the groups. Prime field extensions. No. Okay. Finally, projective planes.

Any questions? I'll wait for a little bit more for any questions before we kind of do like a conclusion of everything and ask for any discussion points. anything if not um then let's quickly go through each part um I guess no questions or what is final plane Um I might be very wrong with this by the way. Um final plane. So um it's a name for projecting plane over finite field f2.

Okay. Actually tried to compute this I think with um sage. Uh I uh they don't have an example code for this. So I'm it might be a little bit hard for me to compute this. But yeah final plane is um I believe just the projective plane over finite field of f2.

So this is the projective plane over F3. No, this is the associative one I think. Is it? Yeah. So yeah, final plane is just a projected plane over F_sub_2 instead of well F3.

Any more questions? So let's let's quickly talk about rings. Uh so um we talk about groups. groups essentially a set of values with an operation or with a um group law. Rings is a set of um or or more like two groups um essentially two groups um because it's but the two groups usually will be on the same set and uh essentially it's a combination of two groups with different group laws very commonly additive and multiplicative um I think here yeah so here it talks about commitive rings of units and is essentially except with two maps um addition and multiplication and using one as the unit such that these properties hold um so yeah that's that's a ring so a ring essentially yeah sets with a tuple I mean it's a I mean it's not a tuple it's a triple In this point um containing a set and two operation actually in this case it includes a unit.

So in this case the unit is one ring just group has two operation. Ring is a you can call it a not a group with so a group is a set with an operation or with with a group law. A ring is a set with two operations or like a set with or two groups with a unit in this case. Yeah, it's not Yeah, it's not really just a group that has two operation, but it's a set with two operations kind of. Yes.

Um yeah I I'm I'm describing it like in a very simple nonformal way. So yes um and let's we can actually jump to field. field is essentially a ring but we want additional additional um properties which we have this neutral element zero and a neutral element of one for multiplicative group and there is an inverse um so there exists how do I put this every non-zero element must have a inverse. So that's that's one of the extra properties that fields have um specifically multiplicative inverse um not additive in inverse. Um yeah so fields are essentially just ring with extra rule to put it in a very simple term with extra um conditions or extra properties that we want.

Um yeah so that's fields and we will usually use prime fields in this case we define square root and um in in situation where I mean when we operate with uh sets or values or groups that don't really okay yeah I think I need to rephrase that better when we operate with fields um square root Um it's so because we work with integer um usually we in a sense ignore um square root that gives us real numbers um in this case right in this specific context of course if you are working with real numbers real number fields that that's not the case right but in this case um we take anything that we can beautifully square root um so x if x= square y and y the square of y will be x right um and we call them we call y essentially the quadratic residue. If y is given and there's no solution x. So if there's no if we cannot square root y then y is the quadratic non-residue. This is just terms that we we are going to talk about later in the book. So yeah, and this is essentially a way of describing if y is a quadratic residue.

Um I'm going to go here. So prime field extension. So prime field extension essentially is a way for us to extend on uh certain prime fields. And this is very useful um when we need And I'm and I'm putting this not very accurately I believe when we need more points essentially uh in a in a field we want to do and this is very helpful again do correct me if I'm wrong especially for those that might be able to explain a little bit nicer um in some cases we do extensions on prime fields because we might want to do some calculations that needs those extra uh points. That's one um that's one of the examples that uh we we we need uh prime extensions.

Um and you can usually do that do an extension um like so I mean well you you need to redefine how addition is done. Um but essentially um addition is done quite straightforward. Um however multiplication is slightly more difficult because it involves um choosing a polomial P um in specifically a reducer polinomial means that it's a it's a polinomial that cannot be further factorized and then using that as a as essentially the mod right um yeah so that's that's essentially what we call a a prime extension you you attempt to extend your um original field with additional points and when you extend it sorry it's basically on polinoms that contain no roots. Yes. Um it yes it adds pol that contain no roots or yeah non-factor.

Yeah not not reducable. Yes. Um and this basically gives it more point. Um if you use I think down below. Yeah.

This shows you how how it's done. So it's essentially it added more point loops right. it extended it to have more polomials in this case. Um again you need to choose a a polomial irreducible polinomial and you put it in and you get this and if you use so this is the entire table for multiplication you can comput it by hand by the way to extend it but if you use s you can actually see you can actually do it quite easily uh if you use a programming language you can usually do it um but yeah that's essentially what we call an prime field extension usually on prime field. Yes.

And so finally projective planes. So let's quickly go through this. So projective planes, how do I put this? I can't really say it as another dimension, but it is technically doing that. So it okay essentially it wants to add a point at infinity so that we can represent it.

We can represent elliptic curves easier and do some computation. That's the point of projected planes. Um you can think about it as I don't think it's very accurate but you can think about it as adding a axis um from 2D to 3D but it's not really that you can think about it like that and we want so this describes it quite nicely. So we want given this field right we want to create a project fields and you want this property of kx * k y * kz k is a subset of field but this so any any k here is equivalent to actually xyz um how this I think this is pretty hard to explain. Um so technically these two are equivalent.

They are they equal to this. Um when we extend it um that's the property of a projective planes in this case that this is ah this is weird to explain. Uh yes, this is equivalent to 011 because of K. This is a little bit weird for me, but I believe this is correct because of the K. Let me see.

Yeah. So, let me see if I can explain a little. Let me formulate my words. Um It's Oh, so intric we is basically a way of defining some points in the curve where the graph actually well extend turns into infinity and and this adds the point back. So it it kind of says yeah include points at infinity and well for parallel lines or for lines that will never intersect in a normal ukidian 2D plane by adding this we we can we say that we make it so that it intersects at infinity.

Thank you. basically it's just to make sure that it it the lines that do not meet meet somewhere or in infinity in a sense it's two straight line that eventually curve and meet at some arbitrary infinity points not particularly regular space. Um yeah, I mean I mean you I think that that's essentially what it's trying to say. Um um the general from my understanding at least the general reason why we want this or we want to define there is a point at infinity and things intersect there is so that some calculations um especially in elliptic curve if you have seen elliptic curve constructions they are I don't know if there's a picture here. Yeah.

So it looks like this sum of curves. Okay, this this is a I don't like this curve but anyways. So there the points here they go to infinity right we to help us calculate you know the points that might be calculated within like behind behind this point we say that these lines will eventually meet in infinity by adding that extra yeah by doing this yep that that's essentially It's it's very hard to visualize, I would say. Um, it's really hard to visualize this, but yeah, it's I guess to a certain it feels like 3D, but it's not really 3D. Um, it intersects somewhere somehow.

Um, yeah. Anyways, great. Yeah, I think that's essentially it. We have 10 more minutes. Any questions?

Anything specifically you want to do like a final discussion before we end this? I I'm pretty happy because uh actually this session I I see a lot of contributions specifically on um cryptographic groups. Um yeah, thank you very much all of you for participating. Um yeah, so any more questions? I will take the silence as a not really.

Um, okay. Since there are no questions, I'm not going to end this right now. most questions and since we've progressed so fast across algebra so the next section actually the next next week I was thinking about covering latic curves but let's do a little bit exercise and let's let's make this slightly more interesting so um from our audience um from our audience someone actually gave me a a suggestion um so and which which I will use. So one thing that I want um all of you here um to participate in um is essentially so uh there is a lot of things here right in in in chapter 4 um I would like you you all um of course no no pressure but I would like you to uh implement groups rings and fields in in whatever programming language you And uh this exercise is to basically help you I mean at least for me this is something that will help me understand it more practically. And um I'll open up a GitHub um and allow you to basically push some PRs to the GitHub um your implementation, right?

And again um if you haven't joined the Telegram group yet, tell me. I I'll share the uh link um here. I'll share the QR here. Um I I'm assuming all of you here already are in the Telegram group. Um yeah but anyways try to implement groups uh rings fields um in whatever programming language you choose and try to make it so that uh yeah wouldn't it just be mod p arithmetic yes it will be however I I want basically make it so that yeah it's essentially exercise right um but I would say if possible don't like allow so allow how what you have implemented like make your what you've implemented into library and um what we'll do so these are all quite simple stuff yes but what we want to do we will do remember to also implement by the way um parallel extension as well try to implement this functionality by the way sage does provide a lot of tools um if you can don't use sage but if you want to you can use sage it's basically python uh it runs python script by the way if you do sage and put python script behind it it actually executes it with all the libraries is there but um if can if you can try not to do that try to implement it from scratch by yourself um try to implement par extension projected claims as well and the point or like more like the idea is um with this implemented we would like or or the the goal is to that so the next time we when we talk about elliptic curves we can start implementing curves um with what we've implemented here right we want to be a build on what we've implemented in chapter 4 and continue on.

This is a little bit of an experiment on my part and also um yeah but but yeah if you yeah please please do that please try to implement gross ring fields the extension the planes and any algorithm in middle right there there's a lot of algorithm that they use to calculate um where is it there is a the hashing yes hashing into groups or hashing into fields try to implement those as well Um yeah. So that's that's something that's a little bit of homework. Um as for next week what we're going to cover. So next week I'm going to put it a little bit chill. So next week we're going to take a look at some of the implementation talk about what we implemented for the first 10 to 20 minutes and we'll cover the short y uh wire straw curve and I think we'll just cover the three curves.

So the wires wire straws curves the Montgomery curves and the twisted out curves. not included in your homework is to implement this. But if you do implement them, it'll be great. So I mean next week's homework essentially is to implement this this tree, right? Um but yeah, so um I I'll put it in in a summary.

Um implement what you've learned in algebra specifically groups, uh rings, fields, and the hashing extension project planes and look into this tree. study into these three that we're going to go through next week. Um, only these three. So 5.1, 5.

2, and 5.3. If you want to, you can implement them first. Um, but uh, next week we'll actually try to implement this. Um, yeah.

So that's essentially it for this week. It's almost time. Any more questions before we end? Great. Um on one more note I'll also I would like to open a notion to actually let us put in our thoughts and discuss and put our notes there from what I've learned we've learned.

Um that's also a very good um suggestion from from from the group here. Um yeah so um I I'll share all that in the group again like in the telegram group again. So again, if you haven't joined yet, tell me. I'll share the link to you. Um, yeah, but I think that's it.

Thank you very much once again for coming and uh, see you guys next week.