# Is this an irreducible polynomial?

I have this polynomial:

$x^8+x^4+x^3+x+1$

and I would like to know if it is irreducible over $\mathbb{F}_q$ with $q=2^8$. My book gives me it is irreducible but matlab says it is not irreducible.

-
This is a polynomial over which ring? It is (certainly!) reducible as a polynomial over $\mathbb C$, for example. –  Henning Makholm Dec 2 '12 at 23:34
I edited the post... I mean over Galois Field $GF(2^8)$ –  Mazzy Dec 2 '12 at 23:35
Reducibility depends on the field. Every polynomial with real coefficients can be written as a product of terms of the type $(x^2 + b x + c)$ and other terms of the type $(x + c)$ with real numbers $b,c$ and perhaps an overall multiplier $a.$ Thi, of course, is just the statement that roots occur in complex conjugate pairs. –  Will Jagy Dec 2 '12 at 23:36
@WillJagy I edited the post. I mean galois finite field –  Mazzy Dec 2 '12 at 23:38

Theorem. Let $P$ be any polynomial of degree $k\ge 2$ with coefficients in $\mathbb F_p$. Then $P$ is reducible over $\mathrm{GF}(p^k)$.

Proof. If $P$ is reducible over $\mathbb F_p$, then the same factorization works over $\mathrm{GF}(p^k)$. So assume $P$ is irreducible over $\mathbb F_p$. Then $\mathbb F_p[X]/(P)$ is isomorphic to $\mathrm{GF}(p^k)$, so the image of $X$ under this isomorphism is a root of $P$. Therefore $P$ has a linear factor in $\mathrm{GF}(p^k)[X]$.

-
So you want say me that my polynomial is reducible. right? –  Mazzy Dec 2 '12 at 23:49
according what you say instead, $1+x^2+x^3+x^4+x^8$ is reducible over GF(2^8), right? –  Mazzy Dec 2 '12 at 23:52
@Mazzy: Um, yes. –  Henning Makholm Dec 2 '12 at 23:53
So why matlab says me that the last one is a primitive polynomial? –  Mazzy Dec 2 '12 at 23:54
@Mazzy: Beats me. My immediate guess would be that it's answering a different question than you think it is (such as whether the polynomial is irreducible over $\mathbb F_2$). –  Henning Makholm Dec 2 '12 at 23:59

If a polynomial of degree 8 over $\mathbb{F}_q$ is irreducible over the finite field $\mathbb{F}_q$, then its splitting field is $\mathbb{F}_{q^8}$, and is thus reducible over $\mathbb{F}_{q^8}$. If a polynomial of degree 8 over $\mathbb{F}_q$ is reducible over the finite field $\mathbb{F}_q$, then it remains reducible over $\mathbb{F}_{q^8}$.

-