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.
and any positive integer 
, there exists a primitive polynomial of degree 
over GF(
). There are
), where 
is the totient function.
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
to equation (◇), the numbers of primitive polynomials over GF(2) are
,
2, .... The following table lists the primitive polynomials (mod 2) of orders 1 through
5.
,
, 
,
,
,
,
,
preceding ones.
