Proving the generator criterion for group $Zp$

tonythestark

1/28/24, 8:18 PM

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

138

1 + 1

number-theory

group-theory

prime-numbers

fgrieu

1/30/24, 11:00 AM

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.

Score:4

Crypto

Wilson

1/28/24, 8:57 PM

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.

+ 4

tonythestark

1/29/24, 7:46 AM

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}

Wilson

1/29/24, 5:58 PM

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

tonythestark

2/2/24, 6:27 PM

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?

Wilson

2/4/24, 4:33 AM

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?

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Proving the generator criterion for group $Zp$

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.