1
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jun 20 '15 at 11:31
  • 1
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jun 20 '15 at 11:38
  • $\begingroup$ @JyrkiLahtonen If this has been asked before, could you provide a link to the old question? $\endgroup$ – Jim Belk Jun 20 '15 at 15:11
  • 1
    $\begingroup$ @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. $\endgroup$ – Jyrki Lahtonen Jun 20 '15 at 17:38
  • $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jun 21 '15 at 11:47
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Some good points. $\endgroup$ – jkabrg Jun 20 '15 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.