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

$$\begin{align} \overline{1} &= \{1,2,4,8,16,32,64,128\} \cr \overline{7} &= \{7,14,28,56,112,224,193,131\} \cr \overline{11} &= \{11,22,44,88,176,97,194,133\} \cr \overline{13} &= \{13,26,52,104,208,161,67,134\} \cr \overline{19} &= \{19,38,76,152,49,98,196,137\} \cr \overline{23} &= \{23,46,92,184,113,226,197,139\} \cr \overline{29} &= \{29,58,116,232,209,163,71,142\} \cr \overline{31} &= \{31,62,124,248,241,227,199,143\} \cr \overline{37} &= \{37,74,148,41,82,164,73,146\} \cr \overline{43} &= \{43,86,172,89,178,101,202,149\} \cr \overline{47} &= \{47,94,188,121,242,229,203,151\} \cr \overline{53} &= \{53,106,212,169,83,166,77,154\} \cr \overline{59} &= \{59,118,236,217,179,103,206,157\} \cr \overline{61} &= \{61,122,244,233,211,167,79,158\} \cr \overline{91} &= \{91,182,109,218,181,107,214,173\} \cr \overline{127} &= \{127,254,253,251,247,239,223,191\} \end{align}$$

For example, $\overline{7} \times \overline{7} = \overline{19}$ 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 = \overline{7}$ and $\beta = \overline{13}$ then any element can be written as $\alpha^i\beta^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 $\overline{1}$ again?

(For example, if $N=32$ then I don't know how to find the period of $\overline{7}$ without trying it thousands or even millions of times.)

I don't have much experience with noncyclic groups and not sure how to approach.

  • $\begingroup$ You could always use GAP. $\endgroup$ – Shaun Jul 15 '18 at 22:41
  • $\begingroup$ What is GAP? Is that software? I would rather understand an algorithm that I can use myself in whatever computing environment I need. $\endgroup$ – Jason S Jul 15 '18 at 22:52
  • $\begingroup$ Yes, it's software. It's completely free. I understand your aversion to using it though. $\endgroup$ – Shaun Jul 15 '18 at 23:03
  • $\begingroup$ 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...? $\endgroup$ – user1729 Jul 16 '18 at 8:18
  • $\begingroup$ 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 $\mathbb{Z}_{2^n-1}^{\ast}$ and then listing the elements of this cyclic group. This gives a list which appears random.) $\endgroup$ – user1729 Jul 16 '18 at 8:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.