- 940

- 155

For GF2, the primitive polynomials are x + (0,1) = x, x+1.

For GF4, we consider primitive-polynomial candidates x

^{2}+ (0,1)*x + (0,1): x

^{2}, x

^{2}+ 1 = (x + 1)

^{2}, x

^{2}+ x = x(x + 1), x

^{2}+ x + 1. That last one is the only primitive polynomial for GF4.

For GF8, we consider primitive-polynomial candidates x

^{3}+ (0,1)*x

^{2}+ (0,1)*x + (0,1): x

^{3}, x

^{3}+ 1 = (x

^{2}+ x + 1)*(x + 1), x

^{3}+ x = x * (x + 1)

^{2}, x

^{3}+ x + 1, x

^{3}+ x

^{2}= x

^{2}* (x + 1), x

^{3}+ x

^{2}+ 1, x

^{3}+ x

^{2}+ x = x*(x

^{2}+ x + 1), x

^{3}+ x

^{2}+ x + 1 = (x + 1)

^{3}.

Thus, GF8 has primitive polynomials x

^{3}+ x + 1 and x

^{3}+ x

^{2}+ 1.

(b) There is a problem here. A basis is easy to define for addition: {1, x, x

^{2}} where multiplication uses the remainder from dividing by a primitive polynomial. The additive group is thus (Z2)

^{3}. The multiplicative group is, however, Z7, and it omits 0. That group has no nontrivial subgroups, so it's hard to identify a basis for it.

(c) That is a consequence of every finite field GF(p

^{n}) being a subfield of an infinite number of finite fields GF(p

^{m*n}), each one with a nonzero number of primitive polynomials with coefficients in GF(p

^{n}). Since each field's primitive polynomials cannot be be factored into its subfields' ones, each field adds some polynomial roots, and thus, there are an infinite number of such roots.

I will now try to show that every finite field has a nonzero number of primitive polynomials with respect to some subfield. First, itself: for all elements a of F relative to F, (x - a) is primitive. Thus, F has N primitive polynomials. For GF(p

^{m*n}) relative to GF(p

^{n}), I will call the number N(m). One can count all the possible candidate polynomials for GF(p

^{m*n}), and one gets

$$ \sum_{\sum_k k m_k = r} \prod_k P(N(k),m_k) = N^r $$

If N is a prime, then the solution is known:

$$ N(m) = \frac{1}{m} \sum_{d|m} N^{m/d} \mu(d) $$

where the μ is the Moebius mu function, (-1)^(number of distinct primes if square-free), and 0 otherwise. I don't know if that is correct for a power of a prime.