ZK Hack Study Group – MoonMath Manual 2024 – Week 2 Part 2

Transcript

okay can you guys see see my screen right now I think you can okay nice all right so let's start uh so the material I prepare for my talk is uh mainly cyclic groups also um we talk about coet leading to approve to the L Ranch theorem okay so the main reference is this AA book uh is uh free is online okay uh this is a pretty nice abstract algebra that does not go too deep so I use that as a reference okay

and let's start with uh isomorphism so in DK and cryptography General uh we don't care about homomorphism we only care about about isomorphism okay so so there's a theory on homomorphism we are not going to cover that we're going to focus on the isomorphic stuff okay so the definition we have two groups one is uh the the set is G uh binary operator is the dot the other is a set H with a binary operator Circle so they are isomorphic if there exists a

bje so bjective mapping means it is both injective and subjective we call that mapping F and uh it is from G to H so it has to satisfy the homomorphism definition which is five of a * B uh pay attention to this times uh so this is the operation in the first group and uh equals 5 a circle 5 b which is the operation in the second group so they are different okay and so a good way to to memorize this is uh consider

this is you do the operation first and then do the map on the right hand side is you do the math first and then do the operation so it's like a yes it's like a flip order symmetry stuff okay so this part is the homomorphism definition together it has to satisfy the projection requirement which you have to show this function f is both subjective and injective to prove that it is bjective so so combining these these two requirements you have a hom uh I mean isomorphism okay so that is the definition let's work

through an example the example I pick is z for Z is isomorphic to the Clic group generated by I this I is just the that famous I in in complex numbers okay so i² equals netive 1 that I okay so the definition is we set f as a function from Z for Z to that cyclic group generated by I so this pointy bracket means CYCC cyclic group generated by this element okay so the uh I think this is wrong I should put colon here but whatever so the

definition of the map is we map n to I to the N power so why does it work because we can find a one to one correspondence by mapping each element to to that element in the other group for example map zero to I to zero power you got one okay map one to I to the one you got I map two to the I to2 you got negative one and map three to I to third you got negative I so you see this we can generate uh uh no I I mean we can map to

every element on the other group okay so we cover everything so that group only contains four elements so plus minus one and plusus I okay H you can see the homomorphism requirement is satisfied because we can break it down to I to the M plus n and these M and N are just uh I mean they are in Z for Z and you can break down that exponentiation into a product I to the m * I to the n and further convert them back to 5 m * 5 n so it satisfy the requirement here okay so the uh the dot

here is just plus the circle here is multiplication so they are different different operations okay so personally I like visualizing this thing in a circle so you can see yeah kind of like we map we map zero to I to zero okay so this is like the visualization of the the one to1 correspondence okay uh we don't need to prove projectivity here because we can find a onet to one correspondence like we literally map every every

element here so we found everything we don't have to prove it so this is the projection this is the homomorphic requirement okay uh do we have questions so far no questions I'm going to continue yeah this is pretty easy for you guys I think um so a theem five be a isomorphism then inverse inverse five the the inverse mapping is isomorphism also okay so because it is isomorphism and the elements the number of of elements in g equals to the number

of elements in h because there is one to one correspondence between them this is pretty easy to understand okay so a biling uh Property Transfers to the other group because they are isomorphism if G is a bilon then H is B if G is cyclic then H is cyclic so basically they are kind of like the same but they are not the the the strict same but they are considered the same in mathematical scenario okay so basically you can think of isomorphism as the group G is equal to the group H yeah

kind of okay uh also has a property saying if G has a subgroup of order n then H has that same subgroup of order n okay and so this theorem basically says the properties transferred to the other group okay um here is a important theorem says if G is a cc group of infinite order then it is isomorphic to the integers okay so G can be anything so so any CC group of infinite order is

isomorphic to the integers any cly group of order n so finite order it is a finite cyclic order uh it is a finite cyclic group of order n then it is isomorphic to Theon Z and a special case of that is if you have a prime Order Group then is isomorphic to zpz so uh so why is a uh why we don't me mention ear is a CLI group of order P because there's a theorem this is the

corer of lrch theorem saying if you have a group of order P then it is cyclic and every non element so so I mean G not equal to not equal to e so any nonidentity element is the generator okay so basically there are P minus one generators so uh this we are not going to talk about it now uh we're going to talk about it in the end of this talk okay and so how do you visualize this I think for the for the first statement I

like think of uh these two number lines Okay so I put Z on the bottom so Z is like a infinite number line okay so I map zero to 8 zero I map one to 81 so on so forth okay so this is the first case you can see we kind of con construct one to one correspondence here but we are not going to prove it formally okay so any CC group of infinite order infinite order visualize it as a number line infinite number line okay is isomorphic to Z because we can find one

to one correspondence uh for second statement uh any cly group of finite order I like to visualize that as a clock as a circle you can see this uh is a cc group you multiply a continuously and then it gets back to a z so this is the identity element okay you go back to a to zero in the end and you can map that finite amount of numbers Z and Z which contains element from Z from zero to n minus one you can map them to to each dot on the clock

kind of construct one to one correspondence okay so they are isomorphic so more formally you have to prove this five maps in from a to the n and this K to a to the K you have to prove the homomorphic requirement also have to show this is a projection okay and this third statement is just a special special case of the second so this is the the consequence of L Ranch the theorem maybe you want to memorize all three okay so you can see kind of uh z z z z pz they are the only special

groups I mean if we study enough theory on Z ZZ Z pz we can apply the same Theory to any other CC group because they are isomorphic they are properties transfer okay so if we study enough theory on these three groups we can apply the same thing to other CPS so that's why these examples are are important and we study them a lot okay okay that's for isomorphism do we have questions so far no questions no questions okay let's

continue so we studied isomorphism right now we are moving to more cycli group Theory uh we covered what is cyly group last week right so um remind you that it is visualized as a clock okay so often time a subgroup will depend entirely on a single element of the group okay so this is the

motivation and how do I know this uh take a few examples for example 3z is the set okay you can say it is generated by three keep adding three so we move to the right or you can say generated by negative3 you start from the right and subtract three to get to the left okay so this one is a cly subgroup of C okay and the generator is three or or negative3 okay so uh another example is H which contains two to the N power

and is a integer uh the op uh the binary operator is multiplication here okay so we expand that set a bit we see the identity one this is 22 Z 22 1 22 or to the left this is two to the to the negative onea -2 okay so the generator is either you multiply two to get from from left to right or you mul multiply inverse of two to get from right to the left so this set is a cc subgroup of the rational numbers under multiplication

okay uh we cover two examples of cly subgroup next is U what is this okay so this is and I think this theorem says how do we construct a cycli subgroup okay so we use this notation pointy bracket a this is uh this refers to a to the K power where K is an

integer suppose this is under multiplication okay and we take any element a and we write down the powers of a this is a subgroup of G and and also this is the smaller subgroup of G that contains a okay uh basically this is just saying uh how to construct a c subgroup from a normal group so you can pick any element from and then write down the powers okay uh yeah if the binary operator is plus then you just say n times a instead of a to the K power

okay and here's a formal definition of that so if if this pointy bracket a equals the entire group G then G is a group generated by a we call a the generator okay uh but that's not always the case because uh usually this pointed bracket a will be a subset of the group so if that happens to be the entire group then then the group G is a cc group otherwise this is just asically sub group okay okay so this is the definition of order

of an element so for any pay attention we are not talking about the order of a in a cyclic group we are talking about in general group might not be cyclic okay so the order of a is the smallest positive integer such that and to uh a to the N power is the identity maybe it uh maybe such n exist so the group is uh no no no I mean if that n exist then a has a finite order and we denote that as this a

bar a modulus a ABS absolute value whatever equals n okay otherwise uh we say the order of the element is infinity so this is pretty easy to understand why we say the smallest positive integer because you can have many thing map to maps to e because you have a to n equals the idty also you can square that what third power is still still e okay so for the order we only care about the the non-trivial one which is the smallest so this so this one okay question so far oh no question you

guys are pretty quiet today no questions right okay let's continue uh I have to emphasize again that the definition we talk about isn't for cyclic group we are talking about for General group a group G that might not be cyclic some element A in that probably have order okay probably the other case you just it does not have that order so is infinite order

okay and example I think we covered this last week uh cly group can have more than one generator so for TMA 60 it can be generated by one so + 1 + 1 + one you reach to all the elements here or you can generate that by five okay so both of them are uh generators okay generator is not unique also not every element is generator for example two is not the generator because it only covers uh 0 two and four which is not Z most 60 uh and it is only a subset of

that okay so two is not generator generator can be one or five generator is not unique generator is not uh like not every element will be a generator okay uh for Z and z in Z case I think I should say or here you know this yeah I think oh wait yeah this is or yeah I'll fix that later so generator of the which is an

infinite cly group you either use gener one to go from left to right you keep adding one or keep keep sub uh subtracting one to go from right to left okay I think this is or yeah and Generator for Z NZ can be one as you see one literally can generate any z z group uh but some other element can also generate that so one is not the only generator you has some other element but it depends on the case okay so it's a case by case uh famous theorem saying very

famous one uh probably you should memorize this is if a group G is Clic then it is a beaing but not the not the reverse so if a group G is billion it doesn't have to be cyclic but if is cyclic has to be a billion so how to prove that I got this idea from TK book okay so the basic idea is just you pick some for example saying we work with addition okay so pick some element R uh because is a cly group it can be represented uh by uh P plus Q so p is uh a keep pading a for x times and Q is

keep addding a for y times so P plus Q or it can be represented as Q Plus P so you just flip the order here first you add a for y times then you add a for X time so this is kind of the a bilon thing okay so uh it's not a formal proof but I think it's easier to understand this way so so so I include here so this is the idea you just break down things uh or you can do multiplication here it doesn't matter okay so the idea is still the same and Theorem every subgroup of cly

group eally this one is pretty easy to remember okay uh a corollary of that is uh the subgroups of Z are just n z so so 2 Z 3 Z 4 Z so on so forth okay uh Z is cyclic also the subgroups and z are also cyclic um coming next oh wait do we have questions so far need to be co- Prime wait which one which one need to be co- Prime

Co Prime I don't think so are you talking about this theorem no I don't think we are using farb to VI generator of G oh okay so what's the condition for a generator oh yes yes yes I think you are right yes that's a uh I think that's the the consequence of log range theorem right

so yeah I think so C Prime for Malo theem or that yeah I remember something or or probably I will cover that somewhere I don't remember generator yeah I think so yes if an element for example in Z and Z if an element is co-prime to the modulus and then it is a generator I think we talk about this last week in the oiler five function some where around there

okay yeah yeah yeah yeah so for zy every element is co- Prime this P therefore everything there other than zero is the generator yeah yeah okay and let's continue oh this is a pretty fun one proposition uh suppose a group G is cylic with order n okay uh it is generated by a then I claim that a to the K power is

the identity if and only if n divice k I think this is pretty obvious so why is it obvious and you have a to the nals E also you can square that or keep adding a to the end to this expression okay you can keep on keep on going you will have NIS K so K here is k = n k = 2 n k = 3 n is always a factor of that okay so this proposition just saying you have multiple you can have many many infinite thing that equals e

but there are some some multiples of I mean some some uh exponential of a to the N okay uh so this proposition keep in mind we are going to use it soon so a very important theorem I think this one is most people don't understand when they take a first course in group Theory okay so this one was pretty confusing to me I just skipped the proof now now I come back I understand proof and so G uh let G be a cc group with order n so same

setup uh G generated by a same setup okay so I claim that the order of a to Decay is n over or gcd k so how does it work so why do we care about the order of a to the K because this is some element in the cyclic group because weall that cycli group is like a clock it's like a circle everything is some some power of the generator okay so generator generates everything a to dek is some element on the clock so I claim that the order of the some some random element on that is n over gcd of K and

N so yes the proof is very interesting let me show you the proof so our goal is to find the smallest integer M the smallest integer M comes from the definition of the order of some element okay so this m basically is just the order of a to DEC that's what we want to show okay so we are looking for this order we call this order M uh that's equivalent to saying a to the K to the m equals to e that's just

the definition of order okay so this is a to the K * i k * n equals e okay so by the proposition above this one and the order m is the smallest integer such that n divides K * m y because a to the k equals to e if and only if and divid by K okay so we are working with a to the K * m so just substitute K * m for K here you will have if and only

if n divides by device K * app okay so they are equivalent so this result directly comes from this proposition we are using this proposition to to prove this theorem okay yeah use that here and then and now we have UND device km so what does it mean we can divide gcd of KN andn on both sides okay so we divide this big chunk of gcd or k KNN on both Sid

uh we can Factor M out because this just is just a definition of of of that middle school algebra okay we can take M out and so now we are left with two big chunks so this chunk and this chunk I claim that they are copre so why are they co-prime I think I think it's easier to work through a concrete example okay so consider 12 and 18 the gcd of them is just six okay so this is 2 * 6 = 12 and 3 * 6 = 18

you for example I'm I am dividing this gcd thing on both of them so 12 divide by 6 2 18 6 is three and the result two and three are just co-prime I personally I call this they are in simplified form but this is not a formal definition is some concept that I created to to help myself understand this okay and so basically two is just this n divide by this gcd big channel three is here so they are co-prime they are co-prime

is the same as saying they don't divide each other because they are co-prime this I think is just a definition of co-prime saying uh the definition is the only common divisor of them is one right you cannot further divide a some divisor out of them concurrently so there co- Prime means this this big chunk does not divide the other chunk so but this hes you know so this was true yeah we have this condition one condition two we can combine them saying Oh so the big chunks they don't divide

each other so the thing on left hand must divide M this must hold otherwise this equation cannot be true you know so so we are going to from this big chunk and our conclusion is and our gcd km must divide M this must be true okay so uh what does it mean is n over gcd km is M times some integer okay so this one so oh no no no no I mean m equals to n / gcd km time times some integer so n will

be some uh some multiples of this okay so we are looking for the smallest integer by definition so what what is the smallest integer it means m equals to that so just one times so we let the multiple be one so this should be the smallest possible integer for m so we got the answer m is the order m is the order okay yeah this is a pretty pretty fun proof do we have questions on this oh no question you guys are smart yeah this one yeah pretty

interesting okay yeah the proof here is pretty interesting okay and so why I said this theorem is important is because it provides a way of counting the number of generators in a finite C click group so how does it work let's say what is this theorem implies this C area Okay so same setup g equals to uh generated by one is a group C group generated by one of order n okay so then a to Decay a to Decay I remind you

is a an element in the CET group because it's a it is a clock everything is some power of the generator it it is so a to the k e uh a to the K is a generator if and only if gcd of K and equals one oh okay I think I answer the question just now okay yeah yeah we were we were talking about this okay so the the the only condition for A2 the K being a generator is it has to be the power has to be co-prime to in yeah yeah I think we worked this uh last week for

uh zma and Z right we we followed the the oiler F function and we Pro this in zma and z and right now is is um we are showing this result can be generalized to to this one so is a uh this is for a general General cyc group so not only z z uh but you should know that any group with order n c group with order n it is isomorphic to zma and Z so those results are related yeah they are same thing okay yeah the number of

generators is just five of n we talked about this last week okay yeah sometimes this is confusing there are many uh theorems you should memorize but uh yeah you can just remember that um such group is all always isomorphic to z z so you prove this in z z and then you can say this result works for such CET groups in general okay uh in the end we take a an example see 16 z uh the co-prime elements from it is 1

3 5 7 9 11 13 15 okay they are all generators so why uh you should check them uh one by one but for Simplicity we are saying um just take n like you can you can multiply n thise this every element from T 16c and you can see that it generates every element in module 16 okay and you should check for all other uh generators but it's waste of time so we are not not going to do it

here okay questions so far no questions nice and the other important thing before [Music] we before I show you the granch theorem is the coess uh this is also a pretty confusing concept for a first course in group Theory so we right here uh definition left coent it is g to Capital H G * Capital H so this one is the the left coet with

representative G and so this set contains every element of the form G * H where H is is any element from the subgroup okay so this H is the subgroup of G uh you just multiply G on the left to every element in h that's pretty much what it is okay so there is also a concept called right coet as you can imagine is you multiply G on the right so this is GH this is HG same thing you just multiply a single

element yeah remember remember this rep uh representative is you pick a single element from the group it's not from the subgroup you pick any element from the group and then you multiply that to every element in the subgroup this is what a coite means okay so so for a concrete example let's say uh for example H equals to zero and three this is a subgroup of Z 6 Z and the order the I should say left coess here okay so all the left coess of uh of uh H with Representative no no no I mean all the

left CO as V of H are the following so z+ H equals 3+ H why because it is z and uh zero and three this one is uh three and six and 6 M 6 is zero so 0 three 3 0 1 4 4 1 2552 you can see the Symmetry here okay so there are only three coess although there are are six elements because uh like two of them are equivalent so 0 plus h equivalent to 3 plus h because you can do the do the

arithmetic here okay so there are only three distinct uh coess here left coess and also a comment here is saying uh since this Zas Z under addition under addition is communative so left coet are just right coet because uh 3 + H equals to H + 3 so is everything is a billion okay here's a LMA uh so this is pretty just uh like a tool for the proof so so they are pretty easy to prove so I'm not going to do it and

the idea is saying the following are equivalent what does it mean is if one of them is true then you can derine for the others so it doesn't mean all the followings are true you know you're just saying that all the followings are equivalent you have to make one statement true for the others to hold so uh usually we care about proving g1h equals to GH uh g2h so so so I I box it here so so so I can pay attention Okay followings are equivalent doesn't

mean following are true always okay so a important theorem uh saying if H is an subgroup of G then left coess left coess of H in G partition G partition G okay or the left CO as of H partition G what does it mean is G will be a d joint Union of left Co of H so that's pretty pretty hard to understand but but but we can visualize it okay so personally I I like to visualize this as a chocolate bar so for example we have a

group uh contains six element G1 to G6 we can visualize the left goess g1h G2 H all of them just partition partition the the group so basically looks like a chocolate bar okay and uh there's a theorem saying each uh the size of each coet is equal to the size of the sub group I'm not going to prove that uh H you can find the proof online easily okay so basically you have to show this first you have to show that the the size of the coite equals to the size of the

subgroup and then you know that different coets of the same subgroup they must have equal size okay so this G is uh you can pick any G you can pick like G1 to G6 as you wish so uh all of the Cod sets have equal size so it is pretty obvious that you can visualize as a chocolate bar with with the same size okay so so this one is yeah pretty nice tool I use to to remember this these theorems so we do a quick proof on on the theorem itself

um uh so our goal is to prove that all the left coze partition G easier way to do that is to prove all the left coet are this one Union and so without loss of generality we say G1 H and G2 H are two coess okay so we we pick two coess and we do a prove on these two that can be generalized to any pair of coet here so so you know this is like a we prove a special case uh and then you

can generalize the proof to to every pair so so the proof holds okay so we pick two coess with a different representative G1 and G2 and we want to show that the they are destroy Union so the the definition of destroy Union is just um either we have the case that g1h this Co intersect with G2 H the the intersection is empty set so that means they are destroyed okay so or we can have G1 H equals to G2 H so they are equal uh I think this you don't have to prove

this I think okay so this one is just like this case is Trivial so we only focus on the first one um for the sake of contradiction we want to prove the intersection is uh the empty set but it is pretty hard to do that because we don't have like a like a condition to start with so for the sake of contradiction we say the uh the intersection is not empty so we can pick any random element a from the intersection then we can Kickstart the proof uh we pick this element a from the intersection it implies two things okay

so the first thing is a is in G1 H the other is a is in G2 H so we have a system of system of equations so two equations the first one corresponds to to the left and the second equation correspond to the right okay yeah because the first coet has all the element of the form G1 * Leo H the other have G2 * Leo H so we can say we have different elements from H H1 and H2 a equals to G1 H1 also a equals to G2 H2 so we can

um solve the equation and say G1 H1 goes to G2 H2 you can multiply H inverse on the right for both sides so you have G1 equals G2 parentheses H2 * H1 inverse the inverse comes from here okay inverse and recall that by the definition of a group the inverse of course is in the group that's a definition okay the the inverse is in the group uh H2 is in the group by by definition also Okay so so

we multiply them they should be in the group by closure so H2 * H1 inverse is in the group of H so we can say because this wrong thing is in h so it equals to G1 so G1 has to be in in no I mean because H2 * h 1 inverse is in h so G2 times that must be G2 Capital H okay so because G1 equals to that so G1 is also in the in the

coet okay and by the LMA above like this LMA we have uh four implies one because of the Symmetry this say G2 is in G1 H you can derive that into G1 is in g2h so four implies one 4 implies one is what we use here okay so that proves that left coine coess partition G so again I think the take away from

this you just visualize this as a CH CP bar this the thing I invent this is pretty smart I think okay yeah yeah just visualize left CO as at this chocolate bar so everything has equal size and they partition the entire group okay so this is the mental picture you should have uh a little bit uh extension I usually see this in the textbook I have to mention it it is the the index so bracket G call H this this notation is the index which means the number of distinct left coets of h g okay so take an concrete example here uh

is a d m 6z we just work out okay so we just work out this example index is three why is that because they overlap they overlap and they overlap there are So-Cal six Coes but they overlap you know so so they are equivalent so the distinct uh number of distinct left goes are just three so the index is three okay do we have questions so far no question nice nice nice okay we are pretty close to the end I'm pretty tired this is long uh so the last page uh I want to

introduce you to LW Theory the this one is definitely the one you should memorize okay so this is the like the most important theorem we discussed today it says let H be a subgroup of G then the order of H divides the order of G so this means the size or the number of elements in h divides the size or the number of elements in G so how large is the ratio and size of G over size of H is just uh the index we just talk about here okay this uh G colon H is the

index so the ratio between those two is just the number of distinct uh left CES okay so a COR uh it is okay yeah this one is pretty General because uh it says for any finite Group G you pick an element from G then the order of the element must divide the size or the number of element G um so you can say that because it is a finite group of course if it is an

infinite group then what will be be Infinity I think right so this is pretty General okay the order of G divides the number of number of elements in G I think this uh I didn't find a proof of it okay but I think the idea of proving it is just think of G as a generator of some cyclic subgroup because you can always you can always always construct a a cly subgroup okay so the that pointy bracket G thing um like the G

thing so this thing does not have to cover the entire group it can be just like a cc subgroup so the elements will be like G to thec power okay uh it can be just like like a small subgroup in the group we consider this uh subgroup cly subgroup generated by z uh by G and we apply L ran theorem on it so since is a cly subgroup therefore it is a it is a subgroup of G the order of this subgroup must divide the order of

G the Big G I mean okay so recall that the order of the generator is just the size of the cly subgroup I think right because for example if I have G to the 3 equals to e then all the all the elements here will be E G G tod2 and G to the3 no there is no G23 because I said G23 is a e so I only have three elements in the subgroup so so the identity G

itself and G square is the only three elements in this sub group okay so the order of the generator is just the size of the cycli subgroup I constructed and by L range that number have to divide the order of the entire group so I think that proves this statement yeah maybe confusing but but but I think yeah that's the idea okay and another important corollary just following this so once we prove this one we can

derive this statement saying oh we have a finite group of order P which is a prime and then G must be cly so this one is pretty important you should memorize it right so any order so any finite order no I mean any finite group of order P it must be cyclic and anything in it so every element other than the identity in it is a generator this will be used in atic curves or finite field a lot so please remember this okay and so for a more thorough explanation I

have that in my article okay so this is my personal block if you are interested in the proof the ideas like how it is used in ECC attacks please just read my article this is pretty clear than what can what I can talk about right now okay so that's the content for today's talk that's everything do we have questions otherwise we can we can stop today that's everything okay so no

questions you are welcome okay let's start for today then if there's no question that's the all the content okay wow that's another hour and a half that's pretty long okay nice nice I think I will stop stop sharing and uh see you guys next week