Irreducible Polynomials & Building Finite Fields

Print preview

Worksheet Irreducible Polynomials & Building Finite Fields

Today we will develop our understanding of polynomial long division and Euclid’s algorithm for finding GCDs with an eye toward using these ideas to construct finite fields of non prime order. The key tool will be the irreducible polynomials, so we’ll also learn more about those objects. If time permits, we’ll then use these to build our first finite field with non prime order. If not, we’ll start there next week!

🔗

Theorem 43. Polynomial Division & Congruence.

Let \(f(x),g(x)\in F[x]\) such that \(g(x)\neq 0\text{.}\) Then there exist polynomials \(q(x)\) (the quotient) and \(r(x)\) (the remainder) such that

\begin{equation*} f(x)=q(x)g(x)+r(x) \end{equation*}

and \(\deg(r(x))\lt\deg(g(x))\text{.}\)

🔗

If \(r(x)=0\text{,}\) we say \(g(x)\) divides \(f(x)\) or \(g(x)\) is a factor of \(f(x)\) and write \(g(x)\mid f(x)\text{.}\)

🔗

We write

\begin{equation*} g(x)\equiv f(x) \pmod{p(x)} \end{equation*}

and say \(g(x)\) is congruent to \(f(x)\) modulo \(p(x)\) if \(p(x)\) divides \(g(x)-f(x)\text{.}\)

🔗

Definition 44. GCD of Polynomials.

Let \(f(x),g(x) \in F[x]\setminus\{0\}\text{.}\) The greatest common divisor (GCD) of \(f(x)\) and \(g(x)\) is the monic polynomial \(d(x)\) of largest degree such that \(d(x)\) divides both \(f(x)\) and \(g(x)\) and is denoted \(\gcd(f(x),g(x))\text{.}\)

🔗

Algorithm 45. Euclid’s Algorithm.

Let \(f(x),g(x)\) be polynomials in \(F[x]\text{,}\) not both zero, with \(\deg(f(x))\geq \deg(g(x))\text{.}\) To compute \(\gcd(f(x),g(x))\text{,}\) execute the algorithm below.

Set \(r_{-1}=f(x),r_0=g(x)\text{.}\) Set \(i=0\text{.}\)
🔗

🔗
Set \(r_{i+1}\) to be the remainder on doing division of \(r_{i-1}\) by \(r_i\text{.}\)
🔗

🔗
If \(r_{i+1}=0\text{,}\) stop and return \(r_i\text{.}\) Otherwise, add \(1\) to \(i\) and return to step 2.
🔗

🔗

🔗

1.

Use Euclid’s algorithm to find the GCD over \(\F_2\) of \(f(x)=x^4+x^2+x+1\) and \(g(x)=x^3+1\text{.}\)

🔗

Solution.

We compute successive polynomial divisions as directed by the algorithm until we hit a remainder of zero, beginning with \(r_{-1}(x)=x^4+x^2+x+1, r_0(x)=x^3+1\text{.}\)

\begin{align} x^4+x^2+x+1 \amp= x(x^3+1)+x^2+1 \amp r_1(x)\amp =x^2+1 \tag{✶}\\ x^3+1\amp= x(x^2+1)+x+1 \amp r_2(x)\amp = x+1\tag{✶✶}\\ x^2+1 \amp= (x+1)(x+1) + 0 \amp r_3(x)\amp =0\notag \end{align}

So the GCD is \(x+1\text{.}\)

🔗

Theorem 46. Bezout’s Identity.

Let \(f(x),g(x)\) be polynomials in \(F[x]\text{,}\) not both zero. Then there exist two polynomials \(s(x),t(x)\) such that

\begin{equation*} s(x)f(x)+t(x)g(x)=\gcd(f(x),g(x))\text{.} \end{equation*}

🔗

2.

Work backwards through your computation of \(\gcd(x^4+x^2+x+1,x^3+1)\) in 1 to find the polynomials \(s(x)\) and \(t(x)\) which satisfy Bezout’s identity for these polynomials.

🔗

Solution.

We start with (✶✶), where we had the remainder equal to the GCD and solve for the GCD to get

\begin{equation*} x+1 = 1(x^3+1)+x(x^2+1)\text{.} \end{equation*}

Now we solve (✶) for \(x^2+1\) to substitute into this equation and collect like terms.

\begin{align*} x+1 \amp= 1(x^3+1)+x((x^4+x^2+x+1)+x(x^3+1)) \\ \amp = x(x^4+x^2+x+1)+(x^2+1)(x^3+1)\text{.} \end{align*}

So we have

\begin{equation*} s(x)=x, \quad t(x)=x^2+1\text{.} \end{equation*}

🔗

Definition 47. Irreducible Polynomials.

A polynomial \(p(x)\in F[x]\) is irreducible over \(F\) if \(\deg(p(x))\gt 0\) and

\begin{equation*} a(x)b(x)=p(x) \end{equation*}

implies that either \(\deg(a(x))=0\) or \(\deg(b(x))=0\text{.}\) A polynomial that is not irreducible is called reducible.

🔗

3.

Give an example of an irreducible quadratic polynomial over \(\R\text{.}\)

🔗

Solution.

A quadratic polynomial which factors into two terms both of degree larger than 0 factors into a product of linear terms and therefore has two roots in \(\R\text{.}\) So pick any quadratic with no roots in \(\R\text{,}\) e.g.

\begin{equation*} x^2+1\text{.} \end{equation*}

🔗

4.

Are there any reducible linear polynomials?

🔗

Solution.

Any product of factors of a linear (degree one) polynomial must be a degree zero and a degree one polynomial since degrees are additive when multiplying. So all linear polynomials over a field are irreducible.

🔗

5.

Find all of the irreducible quadratic and cubic polynomials over \(\F_2\text{.}\)

🔗

Solution.

Quadratics. There are four quadratic polynomials over \(\F_2\) and as above we only need to check for linear factors (note also that there are three possible products of two linear polynomials).

\begin{align*} x^2 \amp= x\cdot x\\ x^2+1 \amp= (x+1)\cdot(x+1)\\ x^2+x \amp= x\cdot(x+1)\\ x^2+x+1 \amp \end{align*}

So the unique quadratic irreducible polynomial over \(\F_2\) is \(x^2+x+1\text{.}\)

🔗

Cubics. There are eight cubic polynomials over \(\F_2\text{,}\) but certainly the four with constant coefficient \(0\) will be reducible since they are divisible by \(x\text{.}\) Of the four remaining two must be reducible and two irreducible, since the reducible ones must be the products

\begin{equation*} (x+1)^3, (x+1)(x^2+x+1) \end{equation*}

as these are the only degree three products of irreducible linear and quadratic polynomials not involving the factor \(x\text{.}\) Multiplying these out shows that the two irreducible cubics over \(\F_2\) are

\begin{equation*} x^3+x^2+1,\quad x^3+x+1\text{.} \end{equation*}

🔗

Note: This sort of counting process of thinking about how many polynomials of degree \(s\) one can form by taking products of irreducibles of degree less than \(s\) and comparing to the number of polynomials of degree \(s\) is how we can show that there must be irreducible polynomials of every degree over a finite field.

🔗

6.

Is \(x^4+x^2+1\) reducible or irreducible over \(\F_2\text{?}\)

🔗

Solution.

Here we have to be careful. To see if a quartic is irreducible it is not enough to check for roots/linear factors since it could be a product of irreducible quadratics. Indeed,

\begin{equation*} x^4+x^2+1=(x^2+x+1)^2 \end{equation*}

so \(x^4+x^2+1\) is reducible over \(\F_2\text{.}\)

🔗

Definition 48. Quotient of a Polynomial Ring.

Let \(F[x]\) be a polynomial ring over a field and \(p(x)\in F[x]\) be an irreducible polynomial. The quotient of \(F[x]\) by \(p(x)\) is the set of equivalence classes of polynomials in \(F[x]\) modulo \(p(x)\) and is denoted \(F[x]/p(x) \text{.}\)

🔗

7.

Take \(F=\F_2\) and \(p(x)\) to be an irreducible quadratic you found in 5. List all of the equivalence classes of \(F[x]/p(x)\) using

Polynomials of degree less than \(p(x)\) as representatives
🔗

🔗
Powers of an element \(\alpha\) which is a root of \(p(x)\) together with \(0\) as representatives. (Bonus: Why does such a root exist now?)
🔗

🔗