# 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, 2017 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{p}.$$ If for some $$x$$ the powers $$x^{\phi(p)/q_i}$$ are all not congruent to 1 modulo $$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.)

• How to get the prime factorization of p-1, unless it is provided. Can you please clarify this part! @Squeamish Ossifrage May 22, 2022 at 19:23

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, 2017 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$ ;-)). Feb 14, 2017 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, 2017 at 17:58