Factoring Polynomials

We know that factoring a polynomial can be radically different depending on which field makes up your coefficient ring. Let’s illustrate this using Magma. We’ll use the polynomial x5 – 5 and try to factor it over three different coefficient fields.

To construct a polynomial ring over the ring of integers, we use the command:

> P<x> := PolynomialRing(Integers());

This assigns P to be the desired polynomial ring and the variable we’ll use is x. Once you have the ring defined, you can create polynomials in that ring, and ask Magma to factor them. Notice, however, that you must tell Magma to think of the polynomial as “living” in that specified ring. Polynomials such as x5 – 5 can live in many rings! Watch what happens as we change the coefficient ring:

> P<x> := PolynomialRing(Integers());
> f := P! x^5 - x;
> Factorization(f);
[
  <x - 1, 1>,
  <x, 1>,
  <x + 1, 1>,
  <x^2 + 1, 1>
]
> P2<x> := PolynomialRing(GF(2));
> f := P2! x^5 - x;
> Factorization(f);
[
  <x, 1>,
  <x + 1, 4>
]
> P3<x> := PolynomialRing(GF(3));
> f := P3! x^5 - x;
> Factorization(f);
[
  <x, 1>,
  <x + 1, 1>,
  <x + 2, 1>,
  <x^2 + 1, 1>
]

Exercise: There are many more commands in Magma for working with polynomials. Define the polynomial ring P5 over the finite field with 5 elements. Then, use the IsIrreducible(f) command to determine if the following polynomials are irreducible. If not, find the factorizations (over GF(5)).

  • x4 + x2 + 1
  • x4 + x3 + 1
  • x4 + x + 1
  • x4 + x2 + x + 1
  • x4 + x3 + x2 + 1