# How can I find the generator of a composite group and $Z_p*$?

I was doing some research on elliptic curves. I know how to find the generator of $Z_p$ (this is a prime group). But I came across the term $Z_p*$ (group containing elements that relatively prime to $p$, which is composite obviously).

So I want to know how to find the generator of a composite group. How can I find the "generator" of a "composite group" (group order is composite)? And how can I find the "generator of $Z_p*$" (field with composite elements ranging from $\{1,2,\dots,p-1\}$)?

• I presume you are talking about additive groups here, and not multiplicative groups? And generators are not unique, so there is no "the generator". – TMM Feb 14 '17 at 15:06

$\newcommand{\Z}{\mathbb{Z}}$If I have understood your question correctly, your goal is to find a primitive root modulo $p$, also called a generator of $(\Z/p\Z)^\times$, knowing that $p$ is prime.

Do you know the prime factorization of $\phi(p) = p - 1$? If you don't, this is hard. If you do, there's at least one common fast case, and there's always a general slow case.

• Fast case. Is $p$ a safe prime—that is, is there another prime $q$ such that $p = 2 q + 1$? If so, then there are only four possible orders, $\{1,2,q,2q\}$, corresponding, respectively, to the subgroups $\{1\}$, $\{1, -1\}$, the quadratic residues, and the whole group. Thus to find a generator of $(\Z/p\Z)^\times$ it suffices to find a quadratic nonresidue other than $-1$.

You can use the law of quadratic reciprocity to quickly pick a generator. For example, if $p \equiv 3 \pmod 8$ or $p = 5$, then $2$ is a quadratic nonresidue and hence a generator; otherwise $p \equiv 7 \pmod 8$, since $p \equiv 3 \pmod 4$ by virtue of being a safe prime above 5, so $-2$ is a quadratic nonresidue and hence a generator.

(Why is this case common? Often the goal is to find a generator for a Diffie–Hellman group, which over finite fields is always done with a safe prime modulus—although in that case usually one seeks a generator of the order-$q$ subgroup instead, i.e. a quadratic residue other than $-1$. See, e.g., RFC 2412, Appendix E ‘The Well-Known Groups’.)

• Otherwise, general case. Let $\phi(p) = p - 1 = q_0^{e_0} q_1^{e_1} \cdots q_{k-1}^{e_{k-1}}$ for primes $q_i$. March through the quadratic nonresidues $x \in (\Z/p\Z)^\times \setminus \{-1\}$, and for each distinct factor $q_i$ of $p - 1$, check whether $$x^{\phi(p)/q_i} \equiv 1 \pmod{\phi(p)}.$$ If for some $x$ the powers $x^{\phi(p)/q_i}$ are all not congruent to 1 modulo $\phi(p)$, then you have found an element of maximal order $\phi(p)$ which is therefore a generator.

(It doesn't hurt to test all elements, but you may be able to skip quadratic residues faster than computing the modular exponentiation.)

Usually $Z_p^*$ denotes the multiplicative group of the finite field $Z_p = {\mathbb F}_p = {\mathbb Z}/p{\mathbb Z}$ of the integers modulo a prime $p$. It is quite well-known that finite subgroups of the multiplicative group of a field are cyclic, i.e., generated by a single element. In the case of the full multiplicative group $Z_p^*$ such a generator is often called a primitive root, but it is a notoriously difficult (= unsolved) problem to find an algorithm that can provable find quickly a primitive root given the prime $p$.

Take also a look at the wikipedia.

• The absence of a fast provable algorithm does not mean it is hard in practice. Just trial and error normally shouldn't take too long (if $p-1$ does not contain too many small factors). – TMM Feb 14 '17 at 16:19
• @TMM: Yep, I should have mentioned that. If you believe in the generalized Riemann hypothesis, there are primitive roots of size $O(\log^6(p))$, so simply trying all values $2, 3, \dots$ works quite efficiently (if you know the factorization of $p-1$ ;-)). – NoPermanentCookiesHere Feb 14 '17 at 17:21
• Depending on the application, $p$ might have been chosen to guarantee that $p - 1$ does not have many small factors, in which case even $O(\log^6 p)$ is pessimistic. (For ed25519 for instance, where $p = 2^{255} - 19$, we have $\phi(p - 1) / (p - 1) \approx 1/3$, so one in three numbers is a primitive root.) – TMM Feb 14 '17 at 17:58