Characterizing generators for the multiplicative group of a finite field.

Question

Fix a finite field $\mathbb{F}_p$ and consider its multiplicative group $\mathbb{F}_p^\times$, which we know is cyclic. Is there an general way to characterize this group's generators (the primitive $(p-1)^{th}$ roots of unity) beyond what I outline below?

Let $a$ be an element of $\mathbb{F}_p^\times$. Since $a$ generating $\mathbb{F}_p^\times$ is equivalent to $a$ being a primitive $(p-1)^{th}$ root of unity, $a$ is a generator if and only if $\dagger$ $a^{(p-1)/t}\neq 1$ for any prime divisor $t$ of $p-1$.

So, if I want to find all the generators of $\mathbb{F}_p^\times$, I would keep choosing group elements and checking if $\dagger$ is satisfied until such an element $\omega$ is found. Then, I know that every generator is of the form $\omega^b$ where $\gcd(b,p-1)=1$.

Is there a better way to find that initial generator $\omega$? By this I mean a way where I'm not just choosing random elements until I find one that works.

Answer 1

Uhh, I don't think so. But generators are pretty plentiful. By that I mean there are $\varphi (p-1)$ generators, out of $p$ choices. We have $\dfrac p{\varphi (p-1)}\in\mathcal O(\log\log p)$. Meaning that the ratio goes off to infinity rather slowly.

You can start by trying simple random elements like $2$ and $3$.

Answer 2

G has exactly $\phi(n)$ generators, and hence the probability of a random element in $G$ being a generator is $$\phi(n) \over n.$$

Using the lower bound for the Euler phi function, this probability can be seen to be at least $${1 \over (6 \ln \ln n)}.$$

For $n = 2^{2048}$, this is ~2.296%. So, you are highly likely to find at least two generators checking 100 random numbers for $n$ of this size.