A primitive polynomial is a polynomial that generates all elements of an extension field from a base field. Primitive polynomials are also irreducible
polynomials. For any prime or prime
power
and any positive integer , there exists a primitive polynomial of degree over GF(). There are

A polynomial of degree over the finite field GF(2)
(i.e., with coefficients either 0 or 1) is primitive if it has polynomial
order .
For example,
has order 3 since

(2)

(3)

(4)

Plugging in
to equation (◇), the numbers of primitive polynomials over GF(2) are

(5)

giving 1, 1, 2, 2, 6, 6, 18, 16, 48, ... (OEIS A011260) for ,
2, .... The following table lists the primitive polynomials (mod 2) of orders 1 through
5.

primitive polynomials

1

2

3

,

4

,

5

,
,
,
,
,

Amazingly, primitive polynomials over GF(2) define a recurrence relation which can be used to obtain a new pseudorandom bit from the preceding ones.