# How to find generator $g$ in a cyclic group?

As generator $g$ is use in DH how to find combination of prime $p$ and $g$? eg: if we choose $p=23$ its generator is $7$ (given in book) how to find it?

-

Mike gave you the answer for the specific question you asked. I'll try to give you an answer to the question you should have asked:

For Diffie-Hellman, what criteria should I use to select a secure $p$ and $g$?

This question is important, because not every large cyclic group is actually secure. It turns out that, for the group $\mathbb{Z}_p^*$, the factorization of $p-1$ is critical.

If $p-1$ has a factor $q$, and $g^{(p-1)/q} \ne 1$, then given $g$ and $g^x \bmod p$, we can determine $x \bmod q$ in $O(\sqrt{q})$ time.

What does this mean? Well, if we pick a $p$ where $p-1$ has a bunch of small factors $q_1, q_2, q_3$, and we give $g$ to be a primitive element (so $g^{(p-1)/q} \ne 1$ for any $q > 1$), then we transmit $g^x \bmod p$ as a part of the DH exchange, the attacker can efficiently derive $x \bmod q_1q_2q_3$; we're effectively giving him $\log_2 q_1q_2q_3$ bits of our secret exponent. This means that, with a random prime $p$ and either a random $g$, or a primitive $g$, we have a good possibility of leaking quite a bit of information.

So, what do we do? Well, first of all, we make sure that $p-1$ has a large prime factor $q$ that we know. There are two common practices:

• Select a prime $p$ with $(p-1)/2$ prime as well (often called a safe prime). If we do that, then $q = (p-1)/2$ is certainly large enough (assuming $p$ is large enough).

• Select a prime value $q$ (perhaps 256 to 512 bits), and then search for a large prime $p = kq + 1$ (perhaps 1024 to 2048 bits). This is called a Schnorr prime

Once we have our values $p$ and $q$, we then select a generator $g$ that is within the subgroup of size $q$. Members of this subgroup have the property that $g^{(p-1)/r} = 1$ for any factors $r$ of $p-1$ other than $q$ (and $p-1$ itself), hence the above observation does not apply.

One easy way of selecting a random generator is to select a random value $h$ between 2 and $p-1$, and compute $h^{(p-1)/q} \bmod p$; if that value is not 1 (and with high probability, it won't be), then $h^{(p-1)/q} \bmod p$ is your random generator.

An alternative method of finding a generator $g$: if you selected a safe prime, and if your safe prime also satisfied the condition $p = 7 \bmod 8$, then the value $g=2$ will always be a generator for the group of size $q$. It won't obviously be a random generator, however, we can also show that, with a safe prime, if you can solve the computational Diffie-Hellman problem with $g=2$, you can solve it with any $g$ (with a polynomial number of queries), hence $g=2$ cannot be weak.

-
There's something that seems confusing in your answer and I hope you can clarify it. If we select a safe prime $p=2q+1$ and we now want to select a generator $g$ within the subgroup of size $q$, you suggest to take a random value $h$ between $2$ and $p-1$ and then compute $h^{(p-1)/q} \mod p$, which would be the same as computing $h^2 \mod p$. If the result of this is not $1$ this definitely means that $h$ is not a generator of the subgroup of order $2$, but this doesn't necessarily mean that it's a generator of the one of order $q$, we still would have to check that $h^q=1 \mod p$, don't we? – LRM Feb 20 '15 at 9:58
@LRM: you misunderstood the pronoun (and I fixed the answer to be clearer); compute $h^2$, and if this is not 1, then $h^2$ is your generator (not $h$ -- I used "it's", and it wasn't clear which that referred to). Then, we needn't bother to check if $(h^2)^q = 1$, as that's $h^{2q} = h^{p-1}$, and Fermat's Little Theorem says that'll be 1. – poncho Feb 20 '15 at 14:23
Oh right, now everything makes sense! So if we have that $h^2 \mod p \neq 1$, then this is at the same time telling us that $h^2$ is a quadratic residue and therefore must be in the subgroup of order $q$. Thanks a lot for you clarification and for having edited your answer. – LRM Feb 20 '15 at 15:03

I'm assuming you meant "how to efficiently find generator $g$ in a cyclic group?"

Small groups
For small values $p$, bruteforce is efficient.

Large groups with known factorization of group order
The order of the group $\mathbb{Z}_p^*$ is $p-1$. The order of every element divides the order of the group, so the factorization of $p-1$ reveals the possible orders of elements. Using this information, one can fairly efficiently find the order of any element in the group. See also Algorithm 4.79.

Note: this will also work for small groups as you should be able to factor $p-1$ for small values of $p$.

Large groups with unknown factorization of group order
There is no efficient method for finding the order of group elements. With DH, however, since you get to choose $p$, there are some things you can do to find generators of the full group $\mathbb{Z}_p$ or a generator of a large cyclic subgroup with in $\mathbb{Z}_p$. See 4.6.1 of HAC Ch 4. See also another question here.

-