4
$\begingroup$

Suppose that a group $Z_p=${$1,2,3......(p-1)$} where p is a prime number. How to Determine the generator/generators of this group? what are the possible method of finding it?

$\endgroup$
3
  • 1
    $\begingroup$ Something is strange here. The cyclic group of order $p$, or more generally the ring of integers mod $p$, includes a zero element, but you've only listed $p-1$ elements with no zero element. Are you perhaps talking about the multiplicative group $U(p):=({\bf Z}/p{\bf Z})^\times$? The generators of the additive group of integers mod $p$ are relatively easy to characterize; characterizing the generators of the multiplicative group $U(p)$ is a very hard problem with no known (or expected, really) general solution. $\endgroup$
    – anon
    Jun 28, 2013 at 6:23
  • $\begingroup$ related ; math.stackexchange.com/questions/124408/… $\endgroup$ Jun 28, 2013 at 6:34
  • $\begingroup$ yes here i talking about multiplicative group.but what will happen in case of cyclic group. $\endgroup$
    – Aria
    Jun 28, 2013 at 6:34

1 Answer 1

5
$\begingroup$

Suppose you can factor the order of the group, $p-1$ (which is not a safe assumption for large $p$). Suppose $p-1$ has prime factorization $p-1 = f_1^{i_1}\cdots f_k^{i_k}$. Then you can test any element $a$ as a generator by computing $a^{(p-1)/f_j} \bmod p$ for every $j\in [1,k]$. If you ever get 1, then $a$ isn't a generator. If you get non-1's every time, then $a$ is. Keep guessing until you find one.

Note that $Z_p^*$ is always cyclic, so there always is a generator. In fact, there are $\phi(p-1)$ of them. If you want generators to be easy to find, you can choose a prime $p=2q+1$ where $q$ is prime since then $\phi(p-1)=\phi(2q) = q-1$ meaning nearly half the group is generators. You need about 2 expected tries to find one.

$\endgroup$
4
  • $\begingroup$ "Suppose you can factor the order of the group, p−1 (which is not a safe assumption for large p)." I'd say it's a very safe assumption. Of course it's not a safe assumption that you can efficiently factor it (that is, you might not actually manage to get the factors in your lifetime), but we know for sure that the factorization exists and can be calculated in a finite (although possibly very large) number of steps. $\endgroup$
    – celtschk
    Jun 28, 2013 at 6:48
  • 5
    $\begingroup$ @cel, I'd say that if you can't do it in your lifetime, then you can't do it. $\endgroup$ Jun 28, 2013 at 7:34
  • 1
    $\begingroup$ In mathematics, I consider "you can do it" as equivalent to "there's an algorithm to do it that is known to halt." Otherwise statements like "you can add 1 to any natural number" would be wrong because at some point you'll have to do so many carry operations that you'll not be able to finish the addition in your lifetime. Not to mention that for a sufficiently large number, you'll run out of resources to write it down. $\endgroup$
    – celtschk
    Jun 28, 2013 at 12:28
  • $\begingroup$ When I said, "suppose you can factor" the "you" is the OP who is (presumably) a human trying to solve a problem. I did not (and would not) say "suppose a factorization exists for $(p-1)$". $\endgroup$
    – Fixee
    Jun 28, 2013 at 22:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .