4
$\begingroup$

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

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

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – TMM Feb 14 '17 at 16:19
  • $\begingroup$ @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$ ;-)). $\endgroup$ – NoPermanentCookiesHere Feb 14 '17 at 17:21
  • $\begingroup$ 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.) $\endgroup$ – TMM Feb 14 '17 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.