# Characterizing generators for the multiplicative group of a finite field.

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.

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