# How to find generator in a finite group?what is generator?

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?

• 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.
– anon
Jun 28, 2013 at 6:23
• Jun 28, 2013 at 6:34
• yes here i talking about multiplicative group.but what will happen in case of cyclic group.
– Aria
Jun 28, 2013 at 6:34

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.
• 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)$". Jun 28, 2013 at 22:30