Thread: Cyclic Group Generators

Hi,

Dealing with integer multiplicative groups and given this:

is a cyclic group (which occurs exactly when has a primitive root) iff is of one of the forms , 4, , or , where is an odd prime and (Shanks 1993, p. 92). The first few of these are , 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, ... (Sloane's A033948; Shanks 1993, p. 84).

Say I take the group so thats as mentioned above, which makes me think any element should be a generator of the group except the identity element.

So the group contains {1, 2, 4, 5, 7, 8}

Now say I try to generate the group using element 4 (modulo 9)





Subgroup of order 3 (fits in with lagrange rule but not equal to G).

What am I doing wrong that gives me a non-cyclic group? (Im very new to group theory and not great with maths generally), am i even using the generator correctly?

I'm basically just trying to understand the p^n rule for odd-primes, and every element of the group being a generator.

Thanks for any help

Originally Posted by tntcoda

Hi,

Dealing with integer multiplicative groups and given this:


Say I take the group so thats as mentioned above, which makes me think any element should be a generator of the group except the identity element.

So the group contains {1, 2, 4, 5, 7, 8}

Now say I try to generate the group using element 4 (modulo 9)





Subgroup of order 3 (fits in with lagrange rule but not equal to G).

What am I doing wrong that gives me a non-cyclic group? (Im very new to group theory and not great with maths generally), am i even using the generator correctly?

I'm basically just trying to understand the p^n rule for odd-primes, and every element of the group being a generator.

Thanks for any help

First, what is that Shanks and Sloane quotes you give above? Second, what is ? Third, I think you're making a big mix of several very different things and I'm no sure how you're dealing with this stuff if, as you say, you're "new at group theory"...!?!

You take the group of units in the ring of (integer) residues modulo 32 (and somehow I feel you'd rather have to deal with the multiplicative group of the FIELD with elements...) , but whatever: we have a nice theorem in group theory that says that the units group in is cyclic of order 6, but NOT all its non-unit elements are generators since this is not a group of order a prime: we have generators here: , and 4 cannot be a generator since and its power is not coprime with 6...For example, as 5 is coprime with 6 so 5 is a generator.

I think it'd be a good idea if you'd explain what is this about, explain the background and the symbols. Perhaps that way there's a chance somebody will be able to explain you something.

Tonio

Thanks for the reply.

The context here is cryptography working in the multiplicative group of integers mod n. Im really just trying to get a basic grasp of group theory so I can understand the cryptography more.

I think it now makes sense why isn't cyclic, because it doesn't have a prime order.

I was somewhat confused though because this page says that the group should be cyclic if the modulus is of the form where p is an odd prime, i still don't really understand why that fails to work with a modulus of 3^2?

If i can explain more on my context and where this is all coming from, part of a cryptosystem im looking at has this step:

Alice generates an efficient description of a cyclic group G of order q with two distinct, random generators g1,g2.

So, I came to the conclusion that if a group is going to have multiple generators it a) needs to be cyclic and b) needs to have a prime order. Does that sound correct?

From here I went to trying the group hoping the p^n (powers of odd primes) rule would work, but as you said it isnt of prime order, so every element wont be a generator.

Does that help explain where my mind is at? Thanks for any advice

Originally Posted by tntcoda

Thanks for the reply.

The context here is cryptography working in the multiplicative group of integers mod n. Im really just trying to get a basic grasp of group theory so I can understand the cryptography more.

I think it now makes sense why isn't cyclic, because it doesn't have a prime order.

I was somewhat confused though because this page says that the group should be cyclic if the modulus is of the form where p is an odd prime, i still don't really understand why that fails to work with a modulus of 3^2?

As previously said, you're confusing stuff here: first, why did you add that * to ?? It doesn't appear at all in Wolfram's page and mathematicians understand that you're talking of the multiplicative group of units in the commutative finite ring of residues modulo , which is of order 6. The additive group of this ring, which is what Wolfram's talking about and denoting by , the hell knows why, IS cyclic of order 9, but it is ADDITIVE, not multiplicative!


If i can explain more on my context and where this is all coming from, part of a cryptosystem im looking at has this step:

So, I came to the conclusion that if a group is going to have multiple generators it a) needs to be cyclic and b) needs to have a prime order. Does that sound correct?

Not even close, I'm afraid to say. Plenty of groups have multiple generators and are not cyclic and, thus, neither of prime order. Take notice that there are cyclic groups of ANY finite order and also one (up to isomorphism) infinite cyclic group.


From here I went to trying the group hoping the p^n (powers of odd primes) rule would work, but as you said it isnt of prime order, so every element wont be a generator.

Does that help explain where my mind is at? Thanks for any advice

I must say that it is strange seeing someone trying to cope with cryptography without having a hefty background in abstract algebra (at least a very good first theory group course), some serious number theory and, if you're trying to reach far, some rather advanced cryptographic systems use elliptic functions stuff and etc.
I'm afraid that it will be a very tough task for you to succeed in this if you don't worry to fill up those gaps in your mathematical education, and worse: it may become pretty disappointing and frustrating to deal with such a thing without understanding much what's going on.

Tonio

Ok thanks very much, I will do some serious work patching up my maths background.