Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

2 Answers

up vote 4 down vote accepted

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

share|improve this answer
    
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
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$). –  Henning Makholm Dec 2 '12 at 23:59
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.