Irreducible Polynomials

A field F is a set of objects along with two operations, + and *, that satisfy the following axioms:

1. F is a commutative group over the + operation 2. F without the zero element is a commutative group over the ⇥ operation 3. Distributivity: for elements a, b, c 2 F ,

• (a+b)⇥c=a⇥c+b⇥c • a⇥(b+c)=a⇥b+a⇥c • F has an additive identity 0 and a multiplicative identity 1

Polynomials in general don’t form a field except in special cases. Consider the set of (n 1)th-degree polynomials (highest power xn1) with coefficients in Zp for prime p, “modulo” an nth-degree polynomial N.

Such a set forms a field if and only if N is irreducible (i.e. it has no roots or cannot be factored into two lesser-degree polynomials).

To multiply two polynomials in such a field, use the replacement rule that you get by setting N = 0, and replace every instance of xn with the appropriate value derived from the replacement rule.

For example, for N = x2 + x + 1 in Z2, (x + 1)(x + 1) = x2 + 2x + 1 = x2 + 1 = x + 1 + 1 = x.

A generator for such a field is a polynomial such that every element of the field can be written as a power of that polynomial.

This app that tests the ten irreducible polynomials for p = 5, n = 2 and determines for each of them, whether x is a generator.

Check out the app here.