How to verify if g is a generator for p?

Question

For learning purpose, supposed I have a 16-digit prime which is 2685735182215187, how do I verify if g is a generator? (p is supposedly a special kind of prime)

Answer 1

Steps:

• Factor $p-1$, that is, find the primes which, multiplied together, produce $p-1$. In your case, $2685735182215186 = 2 \times 1342867591107593$

• For each prime factor $q$ of $p-1$, verify that $g^{(p-1)/q} \not\equiv 1\pmod p$

If every such $q$ verifies (that is, they were all not 1), then $g$ is a generator.

Answer 2

In general, proving that $g$ is a primitive root (often called a generator) of a cyclic group is fairly simple. Note this holds true for non prime modulo as well

Step 1:

Verify that $0\leqslant g \lt p$ and $(g,p)=1$

In other words, verify that $g$ is less than p but greater than or equal to 0, and that $g$ and $p$ are coprime.

Where $g$ is the element of the group in question and p is the modulus being used (or: $\mathbb{Z}_p$).

Step 2:

Calculate $\phi(p)$ where $\phi$ is the Totient Function. If it happens that $p$ is prime, $\phi(p)=p-1$

Then break $\phi(p)$ into it's prime factors such that $\phi(p)=\prod\limits_{i}q_i^{r_i}$ Where each $q_i$ is a prime factor and $r_i$ is the power that prime factor is raised to.

(This notation simply implies that $\phi(p)$ is to be broken down into it's prime factors $q_i$ such that $\phi(p)=q_1^{r_1}\times q_2^{r_2}\times ...$)

Verify that $g^{\phi(p)/q_i}\not\equiv 1 (mod p)$ $\forall q_i$

Ignore the power $r_i$ for this calculation.

Assuming these conditions are met, $g$ is a generator of $\mathbb{Z}_p$.

---

Example:

Let $p=101$, $g=2$.

Step 1:

$0\leqslant 2 \lt 101$ $\checkmark$

and

$(2,101) = 1$ $\checkmark $

Which can be checked using the Extended Euclidean Algorithm if $p$ is not prime (however, 101 is prime, so 2 is most definitely coprime to it).

Step 2

Calculate $\phi(p)=p-1=\phi(101)=101-1=100$ (Assuming $p$ is prime).

Now that we know $\phi(101)=100$, we can break it down into it's prime factors. Check that:

$100=2^2\times5^2$

This means that our $q_1=2, q_2=5$. Remember that we ignore the powers $r_i$ of each of the prime factors for our computations.

Finally, we check:

$2^{\phi(101)/q_1}=2^{(101-1)/2}=2^{50}\equiv100\not\equiv1(mod 101)\checkmark$ $2^{\phi(101)/q_2}=2^{(101-1)/5}=2^{20}\equiv95\not\equiv1(mod 101)\checkmark$

$\therefore g$ is a generator $mod 101$.

(Read: therefore $g$ is a generator $mod 101$.)

Note that this process is to be done $\forall q_i$, in our case there were only two.

(Read: note that this process is to be done for all $q_i$...)

---

In your example, and in practical examples, $p$ is very large. First, confirming that $p$ is prime can be difficult. Second, factorizing $\phi(p)$ into it's prme factors can be quite difficult. I recommend implementing an algorithm to help you, such as Pollard's rho algorithm (although there are others that'll work, like trivial division).

Answer 3

$p = 2685735182215187$ is prime, and $p - 1 = 2q$ where $q = 1342867591107593$ is prime, so the only possible orders of $g$ are $\{1, 2, q, 2q\}$, corresponding respectively to

• $g \equiv 1 \pmod p$,
• $g \equiv -1 \pmod p$,
• $g$ is a nontrivial quadratic residue modulo $p$, i.e. there is some $h \notin \{0,\pm1\}$ such that $g \equiv h^2 \pmod p$, and
• $g$ is a nontrivial quadratic nonresidue modulo $p$, which in this case generates the whole group.

If $g$ is neither $1$ nor $-1$, it suffices to compute the Legendre symbol of $g$, $$(g|p) := g^{(p - 1)/2} \bmod p = g^q \bmod p,$$ which is 1 if $g$ is a quadratic residue and 0 or -1 if it is not. Obviously you can compute $g^q \bmod p$ directly, as in poncho's answer which applies more generally, but for many values of $g$, there are special cases which you can test much more easily by the quadratic reciprocity theorem, that, for distinct odd primes $a$ and $b$, $(a|b) = -(b|a)$ if $a \equiv b \equiv 3 \pmod 4$, whereas $(a|b) = (b|a)$ if either $a \equiv 1 \pmod 4$ or $b \equiv 1 \pmod 4$.

• $3 \equiv p \equiv 3 \pmod 4$, so $(3|p) = -(p|3) = -p^{(3 - 1)/2} \bmod 3 = -p^1 \bmod 3 = 1$, so 3 is a quadratic residue and thus is not a generator of the whole group.
• $5 \equiv 1 \pmod 4$, so $(5|p) = (p|5) = p^{(5 - 1)/2} \bmod 5 = p^2 \bmod 5 = 4 \bmod 5 = -1$, so 5 is a quadratic nonresidue and thus is a generator of the whole group.
• The second supplement to the quadratic reciprocity theorem is that $g = 2$ is a quadratic residue modulo $p$ if and only if $p \equiv \pm 1 \pmod 8$. In this case, $p \equiv 3 \pmod 8$, so 2 is a quadratic nonresidue and thus is a generator of the whole group.