# Is finding generators of finite fields hard?

Task: Given $n$, find a generator of $GF(n)^*$.

Is there any evidence this is hard? Maybe a reduction from another problem presumed hard?

Finding the orders of elements should be hard because I think it can be used to find factors. The order of an element divides the order of the group, so if you pick random elements and find their orders then you can find random factors.

I'm not sure if deciding whether an element is a generator is hard, or if finding a generator (a weaker problem) is hard.

I will give a bounty to an especially good answer.

• This question has been asked before. At one of the previous incarnations TonyK referred to this arXiv submission. The published papers it cites (and refers to in the first couple of pages) should give you enough peer reviewed evidence. – Jyrki Lahtonen Jun 20 '15 at 11:31
• And a generator of $GF(p^n)^*$ is called a primitive element of the field. If you use that buzzword for searching the finite-field tag on our site, the hits are all to relatively small fields. – Jyrki Lahtonen Jun 20 '15 at 11:38
• @JyrkiLahtonen If this has been asked before, could you provide a link to the old question? – Jim Belk Jun 20 '15 at 15:11
• @JimBelk, sorry about not doing that right away. A near duplicate is here. Bill Cook gives another arXiv-link here. There are other questions asking for primitive elements in a specific field. The ones my search found involved relatively small fields, where we e.g. know the factorization of $q-1$, and can take advantage. – Jyrki Lahtonen Jun 20 '15 at 17:38
• The largest field that I found studied on our site is $GF(2^{19}\cdot41+1)$ looked at here. The question really is a DLP problem, but during the solution the candidate primitive element is verified. You see that the simple factorization of $q-1$ is crucial. – Jyrki Lahtonen Jun 21 '15 at 11:47

## 1 Answer

Yes, and no. There's no known algorithm for finding a generator, but your chances of picking one at random ($\frac{\phi(p^n - 1)}{p^n - 1}$) are "pretty good" (I can't recall the exact limit for this expression, but I believe it's somewhere around 46%).

It is not hard to see that this question is intimately related to knowing the exact distribution of primes amongst the integers, an unanswered question that remains of great interest to many (the asymptotic distribution is the best we have, I think).

• Some good points. – jkabrg Jun 20 '15 at 17:15