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.