Question about irreducible polynomials over a finite field. 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

*

*$P$ divides $X^{q^n}-X$;


*$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)$?
 A: 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).

A: 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.
A: 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.
