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}$.
On
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.
On
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.
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.