1
$\begingroup$

In this post the top answer says that for $\mathbb Z_p^*$, $k$, the order of an element $g$, divides p-1. Then it was concluded that this entails we can check if $g$ is a generator by checking if $g^k\bmod p\ne1$, with $k=(p-1)/q$ for $q$ each of the distinct prime factors of $p-1$.

Why does the first claim being true entail the conclusion that the test is valid?

$\endgroup$
3
  • $\begingroup$ Do you mean the order of the group $\mathbb{Z}_p^*$ or do you mean the order of each element in the group? Suggest an edit here. $\endgroup$
    – Lev
    Oct 19, 2022 at 0:05
  • $\begingroup$ @Lev made the edit $\endgroup$
    – John Rawls
    Oct 19, 2022 at 0:13
  • $\begingroup$ slightly tweaked it, hope thats okay. Hope my answer below helps. $\endgroup$
    – Lev
    Oct 19, 2022 at 0:17

2 Answers 2

1
$\begingroup$

The quoted post states that for prime $p$, the order $k$ of any element $g$ of $\mathbb Z_p^*$ divides $p-1$. That is because $\mathbb Z_p^*$, or equivalently $\{1,\ldots,p-1\}$, is a group of $p-1$ elements under multiplication modulo $p$, and then a consequence of (one of) Lagrange's theorem.

If an element $g$ has order $k$ that divides $p-1$, then by definition of divides there is some (uniquely defined) integer $u\ge1$ such that $p-1=k\,u$. The element $g$ is of order $p-1$ if and only if that $u$ is $1$.

If $u$ is not $1$, then there is some prime $q$ dividing $u$ (thus $q$ dividing also $p-1)$, and some integer $v\ge1$ with $u=q\,v$, thus with $p-1=k\,q\,v$; and since $g$ has order $k$, it holds $g^k\bmod p=1$, therefore $\left(g^k\right)^v\bmod p=1$, therefore $g^{k\,v}\bmod p=1$, therefore $g^{(p-1)/q}\bmod p=1$.

Hence if $g$ is not of order $p-1$, then there is some prime $q$ dividing $p-1$ such that $g^{(p-1)/q}\bmod p=1$.

By contraposition, if for every prime $q$ dividing $p-1$ it holds $g^{(p-1)/q}\bmod p\ne1$, then $g$ is of order $p-1$.

Note: sometime, $p$ is chosen as a safe prime, meaning $p$ and $(p-1)/2$ are prime. A test that $g$ is a generator (that is, has the maximal order $p-1$) then boils down to $g^2\bmod p\ne1$ (equivalently, $g\bmod p\ne1$ and $g\bmod p\ne p-1$ ) and $g^{(p-1)/2}\bmod p\ne1$. For a test that $g$ has (prime) order $(p-1)/2$, replace that last test with $g^{(p-1)/2}\bmod p=1$.

$\endgroup$
2
  • $\begingroup$ why is it important that the order of g is p-1? $\endgroup$
    – John Rawls
    Oct 20, 2022 at 1:30
  • 1
    $\begingroup$ @John Rawls: in some applications, we want $x\mapsto g^x\bmod p$ to be a bijection of the set $\{1,\ldots,p-1\}$; that's equivalent to $g$ having order $p-1$. In some others (including textbook Diffie-Hellman), that's customary, even though it would be as good to have $g$ of prime order $(p-1)/2$. $\endgroup$
    – fgrieu
    Oct 20, 2022 at 5:50
1
$\begingroup$

Because if $g^k \neq 1 \mod p$ for all the possible choices of $k$, then that implies that the order of $g$ is strictly greater than all the values of $k$. i.e. the order of $g$ is $p-1$

To see this, suppose that the test concludes with $g^k \neq 1 \mod p$ for all $k$, but that there exists an integer $m < p-1$ such that $g^m = 1 \mod p$. That is, $g$ is not a generator of the group. As an exercise, try these steps:

  1. Show that $m$ must divide one of the values of $k$.
  2. Hence show that $g^k = 1 \mod p$ (for the $k$ above).

(2) is a contradiction.

$\endgroup$
6
  • $\begingroup$ dont we want to have $g^k \ne1 \bmod p$? I thought g is a generator iff $g^{(p-1)/q} \ne 1 \bmod p$ $\endgroup$
    – John Rawls
    Oct 19, 2022 at 0:31
  • $\begingroup$ also how do we demonstrate m must divide one of the possible k values? $\endgroup$
    – John Rawls
    Oct 19, 2022 at 0:36
  • $\begingroup$ Exactly. (2) leads to a contradiction in the assumption that $m$ was not equal to $p-1$. $\endgroup$
    – Lev
    Oct 19, 2022 at 1:07
  • $\begingroup$ Well, that should follow from the fact that $m$ is not $p-1$, or any of the $k$s and that $m$ divides $p-1$. $\endgroup$
    – Lev
    Oct 19, 2022 at 1:09
  • 1
    $\begingroup$ Well we want a generator of the group. If you keep taking powers of a generator, you get every element in the group. A generator is an element which has the same order as the group. This is useful in a manner of ways. We can even write the group as $\langle g \rangle$. That is, the group generated by g (with the group operation given). $\endgroup$
    – Lev
    Oct 20, 2022 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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