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)
-
3$\begingroup$ 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). $\endgroup$– puzzlepalaceMar 26, 2019 at 17:45
-
$\begingroup$ @puzzlepalace sorry, I'm still confused about q. Where do I actually get the q? $\endgroup$– KenMar 26, 2019 at 18:43
-
$\begingroup$ 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. $\endgroup$– puzzlepalaceMar 26, 2019 at 18:54
-
$\begingroup$ @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. $\endgroup$– KenMar 26, 2019 at 19:03
-
$\begingroup$ @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? $\endgroup$– KenMar 26, 2019 at 19:05
3 Answers
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.
-
$\begingroup$ 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? $\endgroup$– KenMar 26, 2019 at 17:13
-
$\begingroup$ @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 $\endgroup$– ponchoMar 26, 2019 at 17:18
-
-
$\begingroup$ @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 useBigInteger::modPow
) or implement a modular exponentiation algorithm yourself. $\endgroup$ Mar 26, 2019 at 20:07 -
1$\begingroup$ What if factoring $p - 1$ is unfeasible? Is it then impossible to verify or are there other techniques you can apply? $\endgroup$– orlpMar 26, 2019 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).
-
$\begingroup$ 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. $\endgroup$– KenMar 27, 2019 at 6:02
-
$\begingroup$ @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. $\endgroup$– TylerMar 27, 2019 at 13:47
-
$\begingroup$ 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^*$ $\endgroup$– ponchoMar 27, 2019 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.