Finding a primitive element of a finite field Let $F = \mathbb{F}_p[x]/(m(x))$, where $m(x)$ is irreducible in $\mathbb{F}_p[x]$. How do I find a primitive element of $F$, i.e., one that generates the nonzero elements of $F$ multiplicatively?
For example, in $\mathbb{F}_{256} = \mathbb{F}_2[x]/(x^8+x^4+x^3+x+1)$, the element $x+1$ has order $255$, so it is a primitive element of $\mathbb{F}_{256}$.
 A: There is a more efficient algorithm, but it involves determining the prime factors of pn-1, then testing for all combinations of those factors. For GF(256) = GF(28), the prime factors of 256-1 = 255 are: 3, 5, 17. The combinations to test for are 3 x 5 = 15, 3 x 17 = 51, 5 x 17 = 85. There's no need to test for 3 x 5 x 17 = 255, since any element raised to the 255 power = 1.
Let α = a potential candidate for a primitive element, then only the first 3 of the 4 cases below have to be tested:
$\alpha^{15} \bmod (x^8+x^4+x^3+x+1) \neq 1$ 
$\alpha^{51} \bmod (x^8+x^4+x^3+x+1) \neq 1$ 
$\alpha^{85} \bmod (x^8+x^4+x^3+x+1) \neq 1$ 
$\alpha^{255} \bmod (x^8+x^4+x^3+x+1) = 1$
(no need to test this case)
Exponentiation by squaring can be used to further speed up this process.
https://en.wikipedia.org/wiki/Exponentiation_by_squaring
A: Pick an element and compute its powers. If these cover all nonzero elements, you have found a primitive element. Otherwise pick an element that you did not cover and start over again.
A: Computationally, you can find it faster than "bruteforcing" (i.e. checking if all powers cover all elements). This is because you can quickly disregard a number from being a generator by checking if it generates a cycle smaller than required by the field. In other words, if $g^n \pmod p = g$ for  $n \in (2, p)$, $g$ is not a generator.
I'm not sure whether the fact that the cycle is not repeating necessarily makes it a generator, but this approach seemed to work for me so far. In fact, at least the opposite should be proven analytically, but I don't have that at hand at the moment and wanted to get this idea out there.
