Primitive Polynomials

Primitive Polynomials

brittneyscheer 04 Apr 2009 23:24

A primitive polynomial is a polynomial that generates all elements of an extension field from a base field. Primitive polynomials are also irreducible polynomials. The following table lists the primitive polynomials (mod 2) of orders 1 through 5.

n	primitive polynomials
1	1 + x
2	1 + x + x2
3	1 + x + x3, 1 + x2 + x3
4	1 + x+ x4, 1 +x3 + x4
5	1 + x2 + x5, 1 + x + x2 + x3 + x5, 1 + x3 + x5, 1 + x + x3 + x4 + x5, 1 + x2 + x3 + x4 + x5, 1 + x + x2 + x4 + x5,

More information and explanations can be found at http://mathworld.wolfram.com/PrimitivePolynomial.html

Last edited on 04 Apr 2009 23:39 by brittneyscheer Show more

Re: Primitive Polynomials

JacquelineJ 05 Apr 2009 02:53

Here are some properties of primitive polynomials:

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

A primitive polynomial must have a non-zero constant term, for otherwise it will be divisible by x. Over the field of two elements, x+1 is a primitive polynomial and all other primitive polynomials have an odd number of terms, since any polynomial mod 2 with an even number of terms is divisible by x+1.

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 xn - 1 is n = pm − 1.

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

The roots of a primitive polynomial all have order pm − 1.

Re: Primitive Polynomials

Aviva Calamaro 06 Apr 2009 01:11

can you explain what you mean by "generates all elements of an extension field from a base field."