Suppose $x \in F_n^{*}$, where $F_n$ is a finite field. Is there an efficient way to test whether x is a primitive element?
This is the best I can come up with: You factor n-1 into all of its factors, f_a. Then you go through each factor, checking the value of $x^{f_a}$ to see if it equals one or not. This doesn't seem that great to me, though. Can you do better?
The Wikipedia article on primitive elements doesn't mention a way of finding these elements. I'd like to add a section to fix this. So in addition, if any of you know any text books or the like that describe methods of finding primitive elements, I'd like to be able to use them as a reference.