# How to verify if g is a generator for p?

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)

• The special kind of prime that you have is called a safe prime. it's a prime of the form $p = 2q + 1$ where $q$ is also prime (as shown by poncho's answer). – puzzlepalace Mar 26 at 17:45
• @puzzlepalace sorry, I'm still confused about q. Where do I actually get the q? – Ken Mar 26 at 18:43
• You can derive $q$ from $p$. In other words, to check if $p$ is a safe prime, you check if $q = \frac{p-1}{2}$ is also prime. – puzzlepalace Mar 26 at 18:54
• @puzzlepalace Thank you for your swift reply. I have computed and checked q=(p-1)/2 and my program returns true (it is indeed a prime). So I'm safe to say that q is also a prime, which means that p is a special kind of prime. – Ken Mar 26 at 19:03
• @puzzlepalace However, I'm still confused about g. I have computed g^(p-1)/2 mod p and g^p-1/(p-1/2) like what poncho has mentioned. The first output is 1342867591052455, and the second output is 0. I'm a little confused about these numbers, do they mean that g is a generator? – Ken Mar 26 at 19:05

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.

• Hey @poncho thanks. I do not understand "For each prime factor q of p−1, verify that g(p−1)/q≢1(mod p)" Is there anyway you can explain it simpler? – Ken Mar 26 at 17:13
• @Ken: Compute $g^{2685735182215186/2} \bmod p$. Compute $g^{2685735182215186/1342867591107593} \bmod p$. If they are both something other than 1, then $g$ is a generator – poncho Mar 26 at 17:18
• Thank you so much @poncho – Ken Mar 26 at 17:24
• @Ken: Java's long type has 64 bits; it's not going to be able to store $2^{1342867591107593}$ without wrapping around. You will need to either switch to BigIntegers (in which case you really should use BigInteger::modPow) or implement a modular exponentiation algorithm yourself. – Ilmari Karonen Mar 26 at 20:07
• What if factoring $p - 1$ is unfeasible? Is it then impossible to verify or are there other techniques you can apply? – orlp Mar 26 at 23:30

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

• Hi @TryingToPassCollege, thank you so much. However, could you give an example? For learning purpose, for example, p = 2685735182104907 and g = 2.. I understand from Step 1 that from the looks of my p and g, it is definitely between 0 and p, and they are definitely coprime because I made a primality check on Java, and p is a prime. As such, g = 2, is a coprime as well. From step 2 onwards, I'm a little confused because tbh I don't understand most of the symbols. I feel like I'm lacking a lot of mathematics experience.. So sorry for all the trouble, as I don't have anyone else to turn to. – Ken Mar 27 at 6:02
• @Ken I have added an example, a few read as descriptions to explain the symbols, and a small summary about applying this method if $p$ is large. Hope this helps. – TryingToPassCollege Mar 27 at 13:47
• Note that non-prime modulii (specially, ones with two distinct odd prime factors) do not have generators; that is, there is no element $g$ where $g^x \bmod n$ is all members of $\mathbb{Z}_n^*$ – poncho Mar 27 at 16:03

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