1
$\begingroup$

I am trying to understand how to find a generator of Zp. How to find generator $g$ in a cyclic group?.
I have heard that we can pick random a Zp and for each primitive d| p-1 check wether:
a^[(p-1)/d] != 1 .If it holds it is a generator, otherwise it is not.

Why does this hold? If a is of order q | p-1 then all I can see is that from Fermat's theorem:
a^(p-1) = a^(q* p-1/q) = 1 mod p

Improve this question
$\endgroup$
1
  • $\begingroup$ You are actually trying to find a generator of the multiplicative subgroup $\mathbb Z_p^*$ of $\mathbb Z_p$ aka $\mathbb Z/p\mathbb Z$. The $*$ denotes exclusion of element(s) without multiplicative inverse, and the use of multiplication as the group law. $\endgroup$
    – fgrieu ♦
    Commented Jan 30, 2023 at 11:00

1 Answer 1

Reset to default
4
$\begingroup$

By Lagrange’s theorem, the order of g must divide p-1. Thus, if the order of g is not any other factor of p-1 besides p-1. The order of g must be p-1.

Improve this answer
$\endgroup$
4
  • $\begingroup$ that's true, but if I understand well you suggest just checking for all d | p-1 that g^d !=1, but I wonder why some people suggest checking g^{p-1/d} $\endgroup$
    – tonythestark
    Commented Jan 29, 2023 at 7:46
  • 2
    $\begingroup$ It's an equivalent statement that you should prove for yourself. Here's an example to get you started. Consider p = 11, p-1 = 10 = 5*2. Notice how g^{10/5}= g^2, g^{10/2} = g^5. Thus, testing g^d for all d | p-1, is the same as testing g^{(p-1)/d}. $\endgroup$
    – Wilson
    Commented Jan 29, 2023 at 17:58
  • $\begingroup$ Here is my new effort: If $ord(a)=d \implies a^d=1 \mod p$ then since $(a^{(p-1)/d})^d=1$ the order of $b=a^{p-1/d}$ must divide d . Assume $p-1/d = k \in N$ then $a^k$ must belong in the subgroup of a.. how can I go on? $\endgroup$
    – tonythestark
    Commented Feb 2, 2023 at 18:27
  • $\begingroup$ Let $D$ be the set of divisors of p-1 except for 1. Consider the set $C= \{(p-1)/d \mid d \in D\}$. Why does this set $C$ contain all divisors of p-1 except p-1? $\endgroup$
    – Wilson
    Commented Feb 4, 2023 at 4:33

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.