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$
1

2 Answers 2

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

$\endgroup$
1
  • $\begingroup$ Thank you! Could you maybe show me the three steps with an example? Like p = 7 or something? It would be amazing! $\endgroup$
    – anon
    Mar 31, 2020 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).

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.