How to find minimal polynomial on finite field ${ GF(2^4) }$

Question

${GF(2^4)}$ ( on these picture ">

How to find minimal polynomial in finite field ${GF(2^4)}$?
I tried to understand law or how my teacher solves it, but I don't know.

Answer 1

It is hard to understand the question, so here i restate (what i think it may be the question):

Which are all irreducible polynomials $p\in \Bbb F_2[x]$ of degree $4$ (so that $F=\Bbb F_2[x]/p$ is a field with $2^4=16$ elements)? Find them...

• either by factorizing $x^{2^4}-x\in \Bbb F_2[x]$, (which is the product of the linear factors $(x-a)\in F[x]$ for all $a\in F$)
• or by computing the minimal polynomial of the generators of $F$.

We factorize first using sage:

sage: R.<x> = PolynomialRing(GF(2))
sage: R
Univariate Polynomial Ring in x over Finite Field of size 2 (using GF2X)
sage: factor(x^16 -x)
x * (x + 1) * (x^2 + x + 1) 
  * (x^4 + x + 1) 
  * (x^4 + x^3 + 1)
  * (x^4 + x^3 + x^2 + x + 1)

(Result was manually rearranged.) Doing this with bare hands is of course cumbersome. The factors of degree four correspond to (all) irreducible polynomials of degree four over $\Bbb F_2$.

To have the human solution, we start with $F$, a / the field with $2^4=16$ elements. (It has characteristic two, so $1=-1$, so there will be no need for a minus sign below...)

Then $F^\times$, with multiplication as operation, is a finite group with $15$ elements, it is cyclic, let $g$ be a "fixed" generator. To be specific, as the OP also mentions, we assume $g$ is a root of the polynomial $$ x^4+x+1\ , $$ so we assume the knowledge of this one irreducible = prime polynomial. (It is easy to show it is irreducible over $\Bbb F_2$, because first of all it has no root in $\Bbb F_2$, and in case of a factorization, we must have it written as a product of two irreducible polynomials $p_1,p_2$ of degree two. But there is only one such polynomial, so $p_1=p_2=x^2+x+1$, but then $p_1p_2=(x^2+x+1)^2=(x^2)^2+x^2+1^2$ is not our polynomial.)

Then $g$ is also a primitive element of $F$ over $\Bbb F_2$, i.e. $F=\Bbb F_2[g]$. Any element $h\in F$ is either zero, or (in terms of the "fixed" $g$) $$ h=g^k\ ,\qquad \text{ where }k\in\{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14\}\ . $$ We write this as a disjoint union of classes w.r.t. the action of the Frobenius morphism $\Phi$, $\Phi h=h^2$. The classes are:

• $0$, the corresponding factor of $x^{16}-x$ is $(x-0)$.
• $g^0=1$, the corresponding factor of $x^{16}-x$ is $(x-1)$.
• $g^1, g^2, g^4, g^8$ (i.e. $g, \Phi g,\Phi^2g,\Phi^3 g$), the corresponding factor of $x^{16}-x$ is $(x-g)(x-g^2)(x-g^4)(x-g^8)=x^4+x+1$.
• $g^3, g^6, g^{12}, g^{24}=g^9$ (i.e. $g^3, \Phi g^3,\Phi^2g^3,\Phi^3 g^3$), the corresponding factor of $x^{16}-x$ is $(x-g^3)(x-g^6)(x-g^9)(x-g^{12})$. And we have to compute it explicitly. It turns out this is the polynomial $x^4 + x^3 + x^2 + x + 1$. Why? We compute its free coefficient, it is not zero, it lives in $\Bbb F_2$, so it is one. The coefficient in $x^3$ is the sum of the roots, $g^3+g^6+g^9+g^{12}=-1+\frac{g^{15}-1}{g^3-1}=-1=1$, since $g^{15}=1$. The polynomial is reciprocal, since together with a root of it, its inverse is also a root, $g^3\leftrightarrow g^{12}$, $g^6\leftrightarrow g^9$ being the pairs of inverse to each other roots. So we also know the coefficient in $x$, which is $x$. The product is thus $x^4 + x^3 + ?\cdot x^2 + x + 1$, and the question mark has to be $1$, else $1$ is a root.
• $g^5, g^{10}$, (i.e. $g^5, \Phi g^5$, and the orbit is closed, since $\Phi^2g^5=g^{20}=g^5$). The corresponding factor of $x^{16}-x$ is $(x-g^5)(x-g^{10})$ and it must be $x^2+x+1$, the only irreducible polynomial of degree two.
• $g^7, g^{14}=g^{-1}, g^{-2}, g^{-4}$ (i.e. $g^7, \Phi g^7,\Phi^2g^7,\Phi^3 g^7$), so the roots are the inverses of the roots for the orbit $g,g^2,g^4,g^8$, the corresponding factor of $x^{16}-x$ is $x^4+x^3+1$, the reciprocal of $x^4+x+1$.