# All generators for modulo p

so I have to find all generators for modulo p. And I thought: isn't there are rule for it? As far as I remember, every number from {1,...,p-1} is a generator because p is a prime. Is that true? Or am I mistaken? What is the rule called?

Or how else do you find generator elements quickly? Do you really have to take each and every element and modulo it with p and figuring out if it returns all numbers n for 0 > n < p-1?

so I have to find all generators for modulo p

Well, there are $$\phi(p-1) = \Omega( p / \log \log p )$$ of them [1]; unless $$p$$ is small, this is infeasible (as there'll just be too many to list). So, we're assume $$p$$ is fairly small (e.g. in the thousands or the millions).

We have a three step process.

• Step 1: factor $$p-1$$; the result of this will be a list of primes $$q_0, q_1, …, q_n$$ (and if any prime appears more than once, you can ignore the second and later occurrences). Because we assumed $$p$$ was fairly small, this is easy.

• Step 2: find a generator. One way to do this is to pick a random value $$g$$ between 2 and $$p-2$$; and check whether $$g^{(p-1)/q_i} \ne 1 \pmod p$$; if this is true for all the primes in the list, then $$g$$ is a generator. If $$g$$ turns out not to be another generator, go back and pick another $$g$$. Since generators are fairly common, this shouldn't take too long.

• Step 3: find all the other generators. You don't need to repeat the above procedure to find the other generators; instead, go through the values $$1 < x < p-1$$ that are relatively prime to $$p-1$$, and compute $$g_x = g^x \bmod p$$; each such $$g_x$$ will be another generator. And, if you go through all the $$x$$ values relatively prime to $$p-1$$, that'll get all of them.

As an example of these three steps, let us consider $$p=31$$.

Step 1: $$p-1 = 2 \times 3 \times 5$$

Step 2: we first pick $$g=26$$. With that, we compute $$g^{30/2} = 30$$, that's not 1. We then compute $$g^{30/3} = 5$$, that's not one. We then compute $$g^{30/5} = 1$$; since that's 1, we reject that $$g$$ and try another.

We then pick $$g=17$$. We have $$g^{30/2} = 30$$, $$g^{30/3}=25$$ and $$g^{30/5} = 8$$, and so 17 is a generator.

Step 3: There are 8 integers in the range $$[1, 30]$$ relatively prime to 30, namely, $$1, 7, 11, 13, 17, 19, 23$$ and $$29$$. Hence, the 8 generators are $$17^1 = 17, 17^7 = 12, 17^{11} = 22, 17^{13} = 3, 17^{17}=21, 17^{19} = 24, 17^{23} = 13$$ and $$17^{29} = 11$$

See, fairly straight-forward...

[1]: the notation $$f(x) = \Omega( g(x) )$$ means that $$f(x)$$ grows at least as fast as $$g(x)$$. Formally, that there exists an $$m$$ such that $$f(x) > m \cdot g(x)$$ is always true (for sufficiently large $$x$$); that is, $$f(x)$$ never gets much lower than $$g(x)$$. It is precisely analogous to the $$O()$$ notation, except that it gives a lower bound ("never much smaller"), rather than an upper one ("never much larger")

• Thank you! Could you maybe show me the three steps with an example? Like p = 7 or something? It would be amazing! – Heinrich Jensen Mar 31 at 23:34

This is not true. In particular, consider $$4\in (\mathbb{Z}/5\mathbb{Z})^\times$$. We have that $$4^2 = 16\equiv 1\bmod 5$$, so $$\langle 4\rangle = \{1, 4\}$$ is not the full group.

The theorem you mention is known as Fermat's little theorem, and it states:

$$\forall x\in (\mathbb{Z}/p\mathbb{Z})^\times$$, $$x^{p-1}\equiv 1\bmod p$$

As you mention, all elements satisfy this. Generators are distinguished in that they satisfy this, but for all $$k < p-1$$ they satisfy $$g^k\not\equiv 1\bmod p$$ (so $$p-1$$ is the "smallest exponent" such that $$g^{p-1}\equiv 1\bmod p$$). As a hint, you don't need to check all $$k < p-1$$ (and you can in fact check a single $$k < p-1$$ which will work in all cases).

• The OP makes more sense if you consider the additive group. – conchild Mar 31 at 7:17
• Actually, it's not true that there will always be a single $k$ for which $g^k \not\equiv 1 \bmod p$ implies $g$ is a generator. Consider $p=7$ and the two nongenerators $g=2$ and $g=6$. For all $0<k<6$, we always have either $2^k \not\equiv 1$ or $6^k \not\equiv 1$ (and hence for any $k$, one of these two nongenerators will show by this test to be a generator). In fact, there will be such a $k$ only if $p$ happens to be a Fermat prime, of which only 5 examples are known (3, 5, 17, 257, 65537). – poncho Mar 31 at 9:34