2
$\begingroup$

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.

  • 0
    This is a polynomial over which ring? It is (certainly!) reducible as a polynomial over $\mathbb C$, for example.2012-12-02
  • 0
    I edited the post... I mean over Galois Field $GF(2^8)$2012-12-02
  • 0
    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.2012-12-02
  • 0
    @WillJagy I edited the post. I mean galois finite field2012-12-02

2 Answers 2

4

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]$.

  • 0
    So you want say me that my polynomial is reducible. right?2012-12-02
  • 0
    according what you say instead, $1+x^2+x^3+x^4+x^8$ is reducible over GF(2^8), right?2012-12-02
  • 0
    @Mazzy: Um, yes.2012-12-02
  • 0
    So why matlab says me that the last one is a primitive polynomial?2012-12-02
  • 1
    @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$).2012-12-02
2

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}$.