Question about irreducible polynomials over a finite field.

Question

If a polynomial $f(x)$ is irreducible over a finite field, does that mean the only factors are $\{1, f(x)\}$?

How would I go about proving a polynomial $f(x)$ is irreducible over a finite field? A bit of searching on StackExchange showed me this:

Irreducibility criterion: A polynomial $P\in\mathbf F_q[X]$ with degree $n$ is irreducible if and only if

1. $P$ divides $X^{q^n}-X$;

2. $P$ is coprime with all $X^{q^r}-X$, $\;r=\dfrac nd$, where $d$ is a prime divisor of $n$.

How would I apply this to $f(x) = x^8 + x^4 + x^3 + x + 1$ over $GF(2^8)$?

Answer 1

Yes ‘$f(x)$ irreducible’ means the only divisors of $f(x)$ are $1$ and $f(x)$, up to a non-zero constant factor.

To apply the criterion to $f(x)$, which has degree $8$, you have to check:

• $f(x)\mid x^{256}-x$ and
• $f(x)$ is coprime with $x^{16}-x$ (via Euclid's algorithm).

Answer 2

By definition a non-zero non-unit element $r$ in a ring $R$ is irreducible if whenever $d$ divides $r$, $d$ is either a unit, or $d$ is the product of $r$ by a unit. So the set of divisors may be considerably larger and contains all elements of the field.

Answer 3

You don't need a CAS for this low degree polynomial $$f(x)=x^8+x^4+x^3+x+1.$$ A pencil & paper solution follows:

First we calculate the remainders $r_k(x)$ of the monomials $x^{2k}, 0\le k\le7$, modulo $f(x)$. These are: $$ \begin{array}{c|c} k& r_k\\ \hline 0&1\\ 1&x^2\\ 2&x^4\\ 3&x^6\\ 4&x^4+x^3+x+1\\ 5&x^6+x^5+x^3+x^2\\ 6&x^7+x^5+x^3+x+1\\ 7&x^7+x^4+x^3+x \end{array} $$ Producing this table is easy. You get $r_{k+1}(x)$ as the remainder of $x^2r_k(x)$ modulo $f(x)$. You only need to do long division, when $x^2r_k(x)$ has degree $\ge8$.

With this table at hand for referrals we can then easily calculate the remainders $p_\ell(x)$ of $x^{2^\ell}$ modulo $f(x)$. This task is tailor-made for exponentiation by squaring. Clearly we get $p_{\ell+1}(x)$ as the remainder of $p_{\ell(x)}^2$ modulo $f(x)$. Remember that, by Freshman's dream in characteristic two, we can square a polynomial from $GF(2)[x]$ term-by-term. When calculating $p_{\ell+1}(x)$ a term $x^n$ in $p_\ell(x)$ produces a term $r_k\equiv x^{2k}$: $$ \begin{aligned} p_0(x)&\equiv&\equiv & x,\\ p_1(x)&\equiv p_0(x)^2\equiv r_1&\equiv &x^2,\\ p_2(x)&\equiv p_1(x)^2\equiv r_2&\equiv &x^4,\\ p_3(x)&\equiv p_2(x)^2\equiv r_4 &\equiv &x^4+x^3+x+1,\\ p_4(x)&\equiv p_3(x)^2\equiv r_4+r_3+r_1+r_0&\equiv&x^6+x^4+x^3+x^2+x,\\ p_5(x)&\equiv p_4(x)^2\equiv r_6+r_4+r_3+r_2+r_1&\equiv&x^7+x^6+x^5+x^2,\\ p_6(x)&\equiv p_5(x)^2\equiv r_7+r_6+r_5+r_2&\equiv&x^6+x^3+x^2+1,\\ p_7(x)&\equiv p_6(x)^2\equiv r_6+r_3+r_2+r_0&\equiv&x^7+x^6+x^5+x^4+x^3+x,\\ p_8(x)&\equiv p_7(x)^2\equiv r_7+r_6+r_5+r_4+r_3+r_1&\equiv&x. \end{aligned} $$ From this second table we see that

• The remainder of $x^{16}-x$ modulo $f(x)$ is $p_4(x)-x\neq0$ meaning that $f(x)$ is not a factor of $x^{16}-x$.
• The remainder of $x^{256}-x$ modulo $f(x)$ is $p_8(x)-x=0$ meaning that $f(x)$ is a factor of $x^{256}-x$.

Therefore we are done.