Mixing
Determining generators of a noncyclic group
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Suppose I have a noncyclic group defined as follows (I'm probably butchering the math here because I don't completely understand):
$G$ consisting of elements which are the set of cosets under multiplication by 2 $bmod 2^N-1$, excluding elements having a common factor with $2^N-1$, using multiplication as the operation.
For example, if $N=8$ then the cosets are
$$beginalign
overline1 &= 1,2,4,8,16,32,64,128 cr
overline7 &= 7,14,28,56,112,224,193,131 cr
overline11 &= 11,22,44,88,176,97,194,133 cr
overline13 &= 13,26,52,104,208,161,67,134 cr
overline19 &= 19,38,76,152,49,98,196,137 cr
overline23 &= 23,46,92,184,113,226,197,139 cr
overline29 &= 29,58,116,232,209,163,71,142 cr
overline31 &= 31,62,124,248,241,227,199,143 cr
overline37 &= 37,74,148,41,82,164,73,146 cr
overline43 &= 43,86,172,89,178,101,202,149 cr
overline47 &= 47,94,188,121,242,229,203,151 cr
overline53 &= 53,106,212,169,83,166,77,154 cr
overline59 &= 59,118,236,217,179,103,206,157 cr
overline61 &= 61,122,244,233,211,167,79,158 cr
overline91 &= 91,182,109,218,181,107,214,173 cr
overline127 &= 127,254,253,251,247,239,223,191
endalign$$
For example, $overline7 times overline7 = overline19$ since 49 is in the coset with 19.
This doesn't have a single generator.
Is there a systematic way to find generators that span the entire group? I can figure out that if I use $alpha = overline7$ and $beta = overline13$ then any element can be written as $alpha^ibeta^j$ for some $i,j$. But I can't seem to generalize this.
And is there a way to find out the period of an element $alpha$ in the group without exhaustively calculating $alpha^i$ until I reach $overline1$ again?
(For example, if $N=32$ then I don't know how to find the period of $overline7$ without trying it thousands or even millions of times.)
I don't have much experience with noncyclic groups and not sure how to approach.
abstract-algebra group-theory
asked Jul 15 at 22:22
Jason S
1,90611617
 |Â
show 2 more comments
up vote
1
down vote
favorite
Suppose I have a noncyclic group defined as follows (I'm probably butchering the math here because I don't completely understand):
$G$ consisting of elements which are the set of cosets under multiplication by 2 $bmod 2^N-1$, excluding elements having a common factor with $2^N-1$, using multiplication as the operation.
For example, if $N=8$ then the cosets are
$$beginalign
overline1 &= 1,2,4,8,16,32,64,128 cr
overline7 &= 7,14,28,56,112,224,193,131 cr
overline11 &= 11,22,44,88,176,97,194,133 cr
overline13 &= 13,26,52,104,208,161,67,134 cr
overline19 &= 19,38,76,152,49,98,196,137 cr
overline23 &= 23,46,92,184,113,226,197,139 cr
overline29 &= 29,58,116,232,209,163,71,142 cr
overline31 &= 31,62,124,248,241,227,199,143 cr
overline37 &= 37,74,148,41,82,164,73,146 cr
overline43 &= 43,86,172,89,178,101,202,149 cr
overline47 &= 47,94,188,121,242,229,203,151 cr
overline53 &= 53,106,212,169,83,166,77,154 cr
overline59 &= 59,118,236,217,179,103,206,157 cr
overline61 &= 61,122,244,233,211,167,79,158 cr
overline91 &= 91,182,109,218,181,107,214,173 cr
overline127 &= 127,254,253,251,247,239,223,191
endalign$$
For example, $overline7 times overline7 = overline19$ since 49 is in the coset with 19.
This doesn't have a single generator.
Is there a systematic way to find generators that span the entire group? I can figure out that if I use $alpha = overline7$ and $beta = overline13$ then any element can be written as $alpha^ibeta^j$ for some $i,j$. But I can't seem to generalize this.
And is there a way to find out the period of an element $alpha$ in the group without exhaustively calculating $alpha^i$ until I reach $overline1$ again?
(For example, if $N=32$ then I don't know how to find the period of $overline7$ without trying it thousands or even millions of times.)
I don't have much experience with noncyclic groups and not sure how to approach.
abstract-algebra group-theory
asked Jul 15 at 22:22
Jason S
1,90611617
You could always use GAP.
– Shaun
Jul 15 at 22:41
What is GAP? Is that software? I would rather understand an algorithm that I can use myself in whatever computing environment I need.
– Jason S
Jul 15 at 22:52
Yes, it's software. It's completely free. I understand your aversion to using it though.
– Shaun
Jul 15 at 23:03
Firstly, I am a bit confused because in your list of sets you seem to be labelling them with primes. This makes sense...but then where are 3, 5, 17...?
– user1729
Jul 16 at 8:18
Secondly, Your group is cyclic for $2^n-1$ prime (a Mersenne prime). (It is a theorem that multiplication mod $p$ gives a cyclic group, and so your group is then a quotient of this cyclic group. Finding a generator of this cyclic group is a well-known problem, and you might want to look up the first chapter of Knuth's Art of Computer Programming, Vol 2, semi-numerical algorithms. This chapter covers random number generators, and these often work by finding a generator of $mathbbZ_2^n-1^ast$ and then listing the elements of this cyclic group. This gives a list which appears random.)
– user1729
Jul 16 at 8:30
 |Â
show 2 more comments
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Suppose I have a noncyclic group defined as follows (I'm probably butchering the math here because I don't completely understand):
$G$ consisting of elements which are the set of cosets under multiplication by 2 $bmod 2^N-1$, excluding elements having a common factor with $2^N-1$, using multiplication as the operation.
For example, if $N=8$ then the cosets are
$$beginalign
overline1 &= 1,2,4,8,16,32,64,128 cr
overline7 &= 7,14,28,56,112,224,193,131 cr
overline11 &= 11,22,44,88,176,97,194,133 cr
overline13 &= 13,26,52,104,208,161,67,134 cr
overline19 &= 19,38,76,152,49,98,196,137 cr
overline23 &= 23,46,92,184,113,226,197,139 cr
overline29 &= 29,58,116,232,209,163,71,142 cr
overline31 &= 31,62,124,248,241,227,199,143 cr
overline37 &= 37,74,148,41,82,164,73,146 cr
overline43 &= 43,86,172,89,178,101,202,149 cr
overline47 &= 47,94,188,121,242,229,203,151 cr
overline53 &= 53,106,212,169,83,166,77,154 cr
overline59 &= 59,118,236,217,179,103,206,157 cr
overline61 &= 61,122,244,233,211,167,79,158 cr
overline91 &= 91,182,109,218,181,107,214,173 cr
overline127 &= 127,254,253,251,247,239,223,191
endalign$$
For example, $overline7 times overline7 = overline19$ since 49 is in the coset with 19.
This doesn't have a single generator.
Is there a systematic way to find generators that span the entire group? I can figure out that if I use $alpha = overline7$ and $beta = overline13$ then any element can be written as $alpha^ibeta^j$ for some $i,j$. But I can't seem to generalize this.
And is there a way to find out the period of an element $alpha$ in the group without exhaustively calculating $alpha^i$ until I reach $overline1$ again?
(For example, if $N=32$ then I don't know how to find the period of $overline7$ without trying it thousands or even millions of times.)
I don't have much experience with noncyclic groups and not sure how to approach.
abstract-algebra group-theory
asked Jul 15 at 22:22
Jason S
1,90611617
Suppose I have a noncyclic group defined as follows (I'm probably butchering the math here because I don't completely understand):
$G$ consisting of elements which are the set of cosets under multiplication by 2 $bmod 2^N-1$, excluding elements having a common factor with $2^N-1$, using multiplication as the operation.
For example, if $N=8$ then the cosets are
$$beginalign
overline1 &= 1,2,4,8,16,32,64,128 cr
overline7 &= 7,14,28,56,112,224,193,131 cr
overline11 &= 11,22,44,88,176,97,194,133 cr
overline13 &= 13,26,52,104,208,161,67,134 cr
overline19 &= 19,38,76,152,49,98,196,137 cr
overline23 &= 23,46,92,184,113,226,197,139 cr
overline29 &= 29,58,116,232,209,163,71,142 cr
overline31 &= 31,62,124,248,241,227,199,143 cr
overline37 &= 37,74,148,41,82,164,73,146 cr
overline43 &= 43,86,172,89,178,101,202,149 cr
overline47 &= 47,94,188,121,242,229,203,151 cr
overline53 &= 53,106,212,169,83,166,77,154 cr
overline59 &= 59,118,236,217,179,103,206,157 cr
overline61 &= 61,122,244,233,211,167,79,158 cr
overline91 &= 91,182,109,218,181,107,214,173 cr
overline127 &= 127,254,253,251,247,239,223,191
endalign$$
For example, $overline7 times overline7 = overline19$ since 49 is in the coset with 19.
This doesn't have a single generator.
Is there a systematic way to find generators that span the entire group? I can figure out that if I use $alpha = overline7$ and $beta = overline13$ then any element can be written as $alpha^ibeta^j$ for some $i,j$. But I can't seem to generalize this.
And is there a way to find out the period of an element $alpha$ in the group without exhaustively calculating $alpha^i$ until I reach $overline1$ again?
(For example, if $N=32$ then I don't know how to find the period of $overline7$ without trying it thousands or even millions of times.)
I don't have much experience with noncyclic groups and not sure how to approach.
abstract-algebra group-theory
asked Jul 15 at 22:22
Jason S
1,90611617
edited Jul 15 at 22:32
asked Jul 15 at 22:22
Jason S
1,90611617
asked Jul 15 at 22:22
Jason S
1,90611617
asked Jul 15 at 22:22
Jason S
1,90611617
1,90611617
You could always use GAP.
– Shaun
Jul 15 at 22:41
What is GAP? Is that software? I would rather understand an algorithm that I can use myself in whatever computing environment I need.
– Jason S
Jul 15 at 22:52
Yes, it's software. It's completely free. I understand your aversion to using it though.
– Shaun
Jul 15 at 23:03
Firstly, I am a bit confused because in your list of sets you seem to be labelling them with primes. This makes sense...but then where are 3, 5, 17...?
– user1729
Jul 16 at 8:18
Secondly, Your group is cyclic for $2^n-1$ prime (a Mersenne prime). (It is a theorem that multiplication mod $p$ gives a cyclic group, and so your group is then a quotient of this cyclic group. Finding a generator of this cyclic group is a well-known problem, and you might want to look up the first chapter of Knuth's Art of Computer Programming, Vol 2, semi-numerical algorithms. This chapter covers random number generators, and these often work by finding a generator of $mathbbZ_2^n-1^ast$ and then listing the elements of this cyclic group. This gives a list which appears random.)
– user1729
Jul 16 at 8:30
 |Â
show 2 more comments
You could always use GAP.
– Shaun
Jul 15 at 22:41
What is GAP? Is that software? I would rather understand an algorithm that I can use myself in whatever computing environment I need.
– Jason S
Jul 15 at 22:52
Yes, it's software. It's completely free. I understand your aversion to using it though.
– Shaun
Jul 15 at 23:03
Firstly, I am a bit confused because in your list of sets you seem to be labelling them with primes. This makes sense...but then where are 3, 5, 17...?
– user1729
Jul 16 at 8:18
Secondly, Your group is cyclic for $2^n-1$ prime (a Mersenne prime). (It is a theorem that multiplication mod $p$ gives a cyclic group, and so your group is then a quotient of this cyclic group. Finding a generator of this cyclic group is a well-known problem, and you might want to look up the first chapter of Knuth's Art of Computer Programming, Vol 2, semi-numerical algorithms. This chapter covers random number generators, and these often work by finding a generator of $mathbbZ_2^n-1^ast$ and then listing the elements of this cyclic group. This gives a list which appears random.)
– user1729
Jul 16 at 8:30
You could always use GAP.
– Shaun
Jul 15 at 22:41
You could always use GAP.
– Shaun
Jul 15 at 22:41
What is GAP? Is that software? I would rather understand an algorithm that I can use myself in whatever computing environment I need.
– Jason S
Jul 15 at 22:52
What is GAP? Is that software? I would rather understand an algorithm that I can use myself in whatever computing environment I need.
– Jason S
Jul 15 at 22:52
Yes, it's software. It's completely free. I understand your aversion to using it though.
– Shaun
Jul 15 at 23:03
Yes, it's software. It's completely free. I understand your aversion to using it though.
– Shaun
Jul 15 at 23:03
Firstly, I am a bit confused because in your list of sets you seem to be labelling them with primes. This makes sense...but then where are 3, 5, 17...?
– user1729
Jul 16 at 8:18
Firstly, I am a bit confused because in your list of sets you seem to be labelling them with primes. This makes sense...but then where are 3, 5, 17...?
– user1729
Jul 16 at 8:18
Secondly, Your group is cyclic for $2^n-1$ prime (a Mersenne prime). (It is a theorem that multiplication mod $p$ gives a cyclic group, and so your group is then a quotient of this cyclic group. Finding a generator of this cyclic group is a well-known problem, and you might want to look up the first chapter of Knuth's Art of Computer Programming, Vol 2, semi-numerical algorithms. This chapter covers random number generators, and these often work by finding a generator of $mathbbZ_2^n-1^ast$ and then listing the elements of this cyclic group. This gives a list which appears random.)
– user1729
Jul 16 at 8:30
Secondly, Your group is cyclic for $2^n-1$ prime (a Mersenne prime). (It is a theorem that multiplication mod $p$ gives a cyclic group, and so your group is then a quotient of this cyclic group. Finding a generator of this cyclic group is a well-known problem, and you might want to look up the first chapter of Knuth's Art of Computer Programming, Vol 2, semi-numerical algorithms. This chapter covers random number generators, and these often work by finding a generator of $mathbbZ_2^n-1^ast$ and then listing the elements of this cyclic group. This gives a list which appears random.)
– user1729
Jul 16 at 8:30
 |Â
show 2 more comments
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2852893%2fdetermining-generators-of-a-noncyclic-group%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
You could always use GAP.
– Shaun
Jul 15 at 22:41
What is GAP? Is that software? I would rather understand an algorithm that I can use myself in whatever computing environment I need.
– Jason S
Jul 15 at 22:52
Yes, it's software. It's completely free. I understand your aversion to using it though.
– Shaun
Jul 15 at 23:03
Firstly, I am a bit confused because in your list of sets you seem to be labelling them with primes. This makes sense...but then where are 3, 5, 17...?
– user1729
Jul 16 at 8:18
Secondly, Your group is cyclic for $2^n-1$ prime (a Mersenne prime). (It is a theorem that multiplication mod $p$ gives a cyclic group, and so your group is then a quotient of this cyclic group. Finding a generator of this cyclic group is a well-known problem, and you might want to look up the first chapter of Knuth's Art of Computer Programming, Vol 2, semi-numerical algorithms. This chapter covers random number generators, and these often work by finding a generator of $mathbbZ_2^n-1^ast$ and then listing the elements of this cyclic group. This gives a list which appears random.)
– user1729
Jul 16 at 8:30