A primitive polynomial of degree n with coefficients in GF(k), the finite field with k elements, has leading coefficient 1 and has a root α that generates the multiplicative group of GF(kn).
That is, every nonzero element of GF(kn) can be written as a power of α.
In my example, I found a primitive polynomial in GF(34) by typing polynomials into Mathematica until I found one that worked.
In[1]:= PrimitivePolynomialQ[x^4 + 2 x + 2, 3] Out[1]= True Since coefficients can only be 0, 1, or 2 when you’re working mod 3, it only took a few guesses to find a primitive polynomial [2].
Brute force guessing works fine k and n are small, but clearly isn’t practical in general.
There are algorithms for searching for primitive polynomials, but I’m not familiar with them.
The case where k = 2 and n may be large is particularly important in applications, and you can find where people have tabulated primitive binary polynomials, primitive polynomials in GF(2n).
It’s especially useful to find primitive polynomials with a lot of zero coefficients because, for example, this leads to less computation when producing De Bruijn cycles.
Finding sparse primitive binary polynomials is its own field of research.
See, for example, Richard Brent’s project to find primitive binary trinomials, i.
e.
primitive binary polynomials with only three non-zero coefficients.
More on binary sequences in the next post on linear feedback shift registers.
*** [1] The same algorithm can be used when k is not prime but a prime power because you can equate sequence of length n from an alphabet with k = pm elements with a sequence of length mn from an alphabet with p elements.
For example, 4 is not prime, but we could have generated a De Bruijn sequence for DNA basepair triples by looking for binary sequences of length 6 and using 00 = A, 01 = C, 10 = G, and 11 = T.
[2] The number of primitive polynomials in GF(pn) is φ(pn – 1)/m where φ is Euler’s totient function.
So in our case there were 8 polynomials we could have found.
.. More details