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

As generator $g$ is used in DH how do you find a combination of prime $p$ and $g$? eg: if we choose $p=23$ and its generator is $7$ (given in the book) how do we find the generator?

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
• @omnomnom; no, they're not the same; if $g^{(p-1)/r} \ne 1$, then the size of the subgroup that $g$ generates has $r$ as a factor (assuming $r$ is a divisor of $p-1$). In contrast, if $g^q \bmod p = -1$, then the size of the subgroup that $g$ generates is either $2$ or $2q$ (assuming $q$ is prime) – poncho Feb 28 at 22:29
• @omnomnom: the context is that $g$ is an element of order $q$; that is, $g^q = 1$. $q$ is a prime divisor of $p-1$, hence for any other prime divisor $r$ of $p-1$, $(p-1)/r$ is a multiple of $q$, that is, $(p-1)/r = kq$ for some integer $k$. So, $g^{(p-1)/r} = g^{kq} = (g^q)^k = 1^k = 1$ – poncho Mar 3 at 17:29

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.