1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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")

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you! Could you maybe show me the three steps with an example? Like p = 7 or something? It would be amazing! $\endgroup$ – Heinrich Jensen Mar 31 at 23:34
2
$\begingroup$

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).

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ The OP makes more sense if you consider the additive group. $\endgroup$ – conchild Mar 31 at 7:17
  • 2
    $\begingroup$ 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). $\endgroup$ – poncho Mar 31 at 9:34

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.