# How to find a generator g for a large prime p?

Trying to implement ElGamal. I have a 1024-bit prime p and now need to find a primitive root g for it. How do you find such a g in an acceptable time? It takes so long, my sage server actually interrupts the calculation.

Here's one easy approach: Pick a large safe prime $p = 2q + 1$ for prime $q$. If you pick $p$ congruent to 1 or 7 modulo 8, then 2 is a quadratic residue modulo $p$, and thus generates a subgroup of large prime order $q$. If you pick $p$ congruent to 3 or 5 modulo 8, then 2 is not a quadratic residue modulo $p$, and thus generates the entire group $(\mathbb Z/p\mathbb Z)^\times$. There are, of course, other choices of generator, which you can use the law of quadratic reciprocity to figure out.
For more general primes $p$, if you know the factorization of $p - 1$, then you can compute generators of all the subgroups independently and combine them with the Chinese remainder theorem. If you look up Schnorr groups, e.g. in DSA parameter generation, you'll find a special case of this for primes $p = kq + 1$ where $q$ is the prime subgroup order of interest: simply pick $h \in (\mathbb Z/p\mathbb Z)^\times$ uniformly at random until you find one with $h^k \not\equiv 1 \pmod p$, and you've found a generator of an order-$q$ subgroup. You can get this by picking a prime $q$ first and varying $k$ until you find a prime $p$ in the desired range.
If you don't know the prime factorization of $p - 1$, then Sage is probably computing it for you! That might take a while if $p - 1$ is 1024 bits long.
• GnuPG, as it turns out, uses exactly the algorithm I described for picking $q$, then $k$ and $p$, then $g = h^k \bmod p$! – Squeamish Ossifrage Dec 27 '17 at 4:16