Hcfyk

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)

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 notequiv 1pmod p$

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

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 $0leqslant 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: $mathbbZ_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)=prodlimits_iq_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_1times q_2^r_2times ...$)

Verify that $g^phi(p)/q_inotequiv 1 (mod p)$ $forall q_i$

Ignore the power $r_i$ for this calculation.

Assuming these conditions are met, $g$ is a generator of $mathbbZ_p$.

Example:

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

Step 1:

$0leqslant 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^2times5^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^50equiv100notequiv1(mod 101)checkmark$
$2^phi(101)/q_2=2^(101-1)/5=2^20equiv95notequiv1(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).

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