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

Question

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\}$)?

Answer 1

$\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.)

Answer 2

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.