Results 1 to 5 of 5

Math Help - Cyclic Group Generators

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    3

    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 {Z_{3^2}}^* so thats p^n 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)

    4\cdot4 = 16 = 7
    7\cdot4 = 28 = 1
    1\cdot4 = 4

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by tntcoda View Post
    Hi,

    Dealing with integer multiplicative groups and given this:


    Say I take the group {Z_{3^2}}^* so thats p^n 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)

    4\cdot4 = 16 = 7
    7\cdot4 = 28 = 1
    1\cdot4 = 4

    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 M_n ? 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 \mathbb{Z}_{3^2}^{*}= the group of units in the ring \mathbb{Z}_{32} of (integer) residues modulo 32 (and somehow I feel you'd rather have to deal with \mathbb{F}_{3^2}^{*}= the multiplicative group of the FIELD \mathbb{F}_{3^2} with 3^2=9 elements...) , but whatever: we have a nice theorem in group theory that says that the units group in \mathbb{Z}_{3^2}^{*}=\{1,2,4,5,7,8\} 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 \phi(6)=2 generators here: 2,5 , and 4 cannot be a generator since 4=2^2 and its power 2 is not coprime with 6...For example, 5 = 2^5 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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    Posts
    3
    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 {Z}_{3^2}^{*} 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 p^n 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 {Z}_{3^2}^{*} 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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by tntcoda View Post
    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 {Z}_{3^2}^{*} 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 p^n 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 \mathbb{Z}_{3^2}?? 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 \mathbb{Z}_{3^2} of residues modulo 3^2=9, which is of order 6. The additive group of this ring, which is what Wolfram's talking about and denoting by M_n , 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 {Z}_{3^2}^{*} 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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2009
    Posts
    3
    Ok thanks very much, I will do some serious work patching up my maths background.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Clifford group generators - matrix form !?
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 24th 2010, 12:02 PM
  2. Cyclic group Generators
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: November 15th 2009, 11:33 AM
  3. Cyclic groups, generators
    Posted in the Algebra Forum
    Replies: 0
    Last Post: November 1st 2009, 06:25 AM
  4. Prove cyclic subroups => cyclic group
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: October 11th 2009, 07:36 PM
  5. Galois Group, generators
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 15th 2009, 08:10 PM

Search Tags


/mathhelpforum @mathhelpforum