Suppose I have a polynomial
f(x) = x^8+x^4+x^3+x+1 over GF(2^8), how do i determine it is reducible or irreducible.
I assume the solution is to find whether the polynomial has roots over GF(2^8) , in that case how do i solve the above polynomial to find the roots.(request easy steps to find the roots with the above example )
$x^8 + x^4 + x^3 + x + 1 | x^{2^8}-x$, where we work in the coefficient field $\mathbb{F}_2$. $f(x)$ is not divisible by the irreducible polynomials of $\mathbb{F}_2[x]$ of degrees 1, 2, or 4. Therefore $f(x)$ is irreducible.
This follows from the theorem:
$g(x) = x^{p^n}-x$ is the product, as $d$ runs through the divisors of $n$, of the distinct irreducible polynomials of $\mathbb{F}_p[x]$ of degree $d$.
Consequently, if your polynomial divides $x^{2^8}-x$ and does not have a factor of order $1, 2, 4, 8, \dots$, it is irreducible. By the rational roots test, it does not have a linear factor. Since $\gcd(f,f')=1$ it has no repeated factor (which easily we could find via $\gcd$). Using the theorem recursively, we find the irreducibles of degree $1$ are $x$ and $x+1$. Of degree $2$, $x^2+x+1$. Of degree $3$, $\frac{x^8}{(x)(x-1)} = (x^3+x+1)(x^3+x^2+1)$, neither of which we need since $3 \not | 8$. Of degree $4$, $x^4+x+1$, $x^4+x^3+1$ and $x^4+x^3+x^2+x+1$. This gives us a complete list of things to factor out of $x^{2^8}-x$ first. Then we (1) know that the quotient has only degree 8 factors, and (2) if your polynomial divides the quotient, your polynomial is a degree 8 irreducible in $\mathbb{F}_{2^8}$.