Exercise 11.2.13

Proof.

(a)

Since $f^{\prime }=1$, $\gcd <!--\; FUNCTION\; APPLICATION\; -->(f,f^{\prime })=1$, so $f$ is separable and we can use Berlekamp’s algorithm directly. If we apply $T$ to each element of the basis, then $$\begin{array}{llll}\hfill 1& \mapsto 1& \hfill & \\ \hfill x& \mapsto x^2& \hfill & \\ \hfill x^2& \mapsto x^4& \hfill & \\ \hfill x^3& \mapsto 1+x+x^4& \hfill & \\ \hfill x^4& \mapsto 1+x+x^2+x^3+x^4& \hfill & \\ \hfill x^5& \mapsto 1+x+x^2+x^3+x^5.& \hfill & \end{array}$$

It follows that the matrix $A$ of $T$ relative to the basis $1,x,x^2,x^4,x^4,x^5$ is

$$A=\left(\begin{array}{cccccc}\hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right)$$

and

$$A-I=\left(\begin{array}{cccccc}\hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \end{array}\right)$$

With Sage :

       (A-1).rank() 

we know that the rank of $A-I$ is $3=6-3$, so $f$ is the product of 3 irreducible factors.

With Sage :

      (A-1).right_kernel() 

we obtain that the kernel of $A-I$ is the span of $v_1,v_2,v_3$, where

$$\begin{array}{llll}\hfill v_1& =(1,0,0,0,0,0)& \hfill & \\ \hfill v_2& =(0,0,1,1,0,1)& \hfill & \\ \hfill v_3& =(0,0,0,0,1,1),& \hfill & \end{array}$$

corresponding to the 3 polynomials

$$\begin{array}{llll}\hfill h_0& =1& \hfill & \\ \hfill h& =x^2+x^3+x^5& \hfill & \\ \hfill h^{\prime }& =x^4+x^5& \hfill & \end{array}$$

By exercise 12 (e), $\gcd <!--\; FUNCTION\; APPLICATION\; -->(f,h-a)$ is a non trivial factor for at least two $a$ in ${𝔽}_2$. Since ${𝔽}_2$ has only two elements, $\gcd <!--\; FUNCTION\; APPLICATION\; -->(f,h)$ and $\gcd <!--\; FUNCTION\; APPLICATION\; -->(f,h-1)$ are two non trivial factors of $f$, and

$$\begin{array}{llll}\hfill & \gcd <!--\; FUNCTION\; APPLICATION\; -->(f,h)=\gcd <!--\; FUNCTION\; APPLICATION\; -->(x^6+x^4+x+1,x^2+x^3+x^5)=x^3+x+1& \hfill & \\ \hfill & \gcd <!--\; FUNCTION\; APPLICATION\; -->(f,h+1)=\gcd <!--\; FUNCTION\; APPLICATION\; -->(x^6+x^4+x+1,1+x^2+x^3+x^5)=x^3+1& \hfill & \end{array}$$

So we obtain two factors of degree 3, therefore

$$f(x)=x^6+x^4+x+1=(x^3+x+1)(x^3+1),$$

but the factors are not necessarily irreducible.

(c)

The two polynomials $$\begin{array}{llll}\hfill & \gcd <!--\; FUNCTION\; APPLICATION\; -->(f,h^{\prime })=\gcd <!--\; FUNCTION\; APPLICATION\; -->(x^6+x^4+x+1,x^4+x^5)=x+1& \hfill & \\ \hfill & \gcd <!--\; FUNCTION\; APPLICATION\; -->(f,h^{\prime }+1)=\gcd <!--\; FUNCTION\; APPLICATION\; -->(x^6+x^4+x+1,1+x^4+x^5)=x^5+x^4+1& \hfill & \end{array}$$

are also nontrivial factors of $f$.

(d)

As $x+1$ divides $x^3+1$, and $x^3+1=(x+1)(x^2+x+1)$, we obtain $$f=x^6+x^4+x+1=(x^3+x+1)(x+1)(x^2+x+1).$$

Since part (a) shows that $f$ has 3 irreducible factors, the factors $x^3+x+1,x+1,x^2+x+1$ are necessarily irreducible, and this is the irreducible factorisation of $f$.