3

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.

enigmaticPhysicist
  • 338
  • It suffices to check the cases where $f_a=(n-1)/p$ for some prime factor $p$ of $n-1$, because all the other factors of $n-1$ are factors of one of those. This doesn't help much though. – Jyrki Lahtonen Apr 13 '16 at 20:27
  • Well, it does help, though. Thanks for the suggestion. Why does it work, though? I don't get it... – enigmaticPhysicist Apr 14 '16 at 12:38
  • Say, you are checking that an element $x$ of $\Bbb{F}_{256}$ has the wanted order $255=3\cdot5\cdot17$. If you verify that none of $x^{255/3}=x^{85}$, $x^{255/5}=x^{51}$, $x^{255/17}=x^{15}$ is equal to $1$, then the order must be exactly $255$. For if you had $x^{17}=1$, then both of $x^{85}$ and $x^{51}$ would also be equal to $1$. Similarly if $x^3$ were $1$, both $x^{51}$ and $x^{15}$ would be, too. You can detect any lower power being $=1$ by checking those maximal divisors of $n-1$. – Jyrki Lahtonen Apr 14 '16 at 14:06

0 Answers0