A primitive polynomial is the minimal polynomial of a primitive element of the extension field GF(p^m).

Properties

Because all minimal polynomials are irreducible, all primitive polynomials are also irreducible.

All primitive polynomials have an odd number of terms and must have a constant term. If a primitive polynomial has no constant term then x can be factored out of it and thus it is not irreducible. If a primitive polynomial has an even number of terms then (x + a) can be factored out of it.

An irreducible polynomial of degree m, F(x) over GF(p) for prime p, is a primitive polynomial if the smallest positive integer n such that F(x) divides xⁿ − 1 is n = p^m − 1.

Over GF(p^m) there are exactly φ(p^m − 1)/m primitive polynomials of degree m, where φ is Euler's totient function.

The roots of a primitive polynomial all have order p^m − 1.

Usage

Field element representation

Primitive polynomials are used in the representation of elements of a finite field. If α ∈ GF(p^m) is a root of a primitive polynomial F(x) then since the order of α is p^m − 1 that means that all elements of GF(p^m) can be represented as successive powers of α:

When these elements are reduced modulo F(x) they provide the polynomial basis representation of all the elements of the field.

Random bit generation

Primitive polynomials define a recurrence relation that can be used to generate random bits.

For example, given the primitive polynomial x¹⁰ + x³ + 1, we start with a user-specified bit seed (it need not randomly be chosen, but it can be). We then take the 10th, 3rd, and 0th bits of it, starting from the least significant bit, and xor them together, obtaining a new bit. The seed is then shifted left and the new bit is made the least significant bit of the seed. This process can be repeated to generate 2¹⁰ = 1024 random bits.

In general, for a primitive polynomial of degree m, this process will generate 2^m random bits before repeating the same sequence.

External links

• MathWorld entry on primitive polynomial
• PlanetMath entry on primitive polynomial