# Polynomial Factoring over a finite field

Ok, so I'm trying to figure out how to factor polynomials over a finite field. My polynomial is x^5 + x^2 + x + 1 and I have to factor over GF(2)

I know the answer is (x+1)^2 * (x^3 + x + 1), because both (x+1)^2 and (x^3 + x + 1) are irreducible. (x+1)^2 is an irreducible polynomial of order 2 and (x^3 + x + 1) is an irreducible polynomial of order 3. But what does that have to do with GF(2)?

I also know that if I were to factor the same polynomial over GF(3) the answer would be (x+1)(x^4 + 2x^3 + x^2 + 1). (x+1) is an irreducible polynomial of order 1 and (x^4 + 2x^3 + x^2 + 1) is an irreducible polynomial of order 4. But again, what does that have to do with GF(3)?

Does GF(2) mean my largest irreducible polynomial can only be an order of 3? And GF(3) my largest can only be an order of 4?

Can someone please verify this? Thanks!

• For $p$ prime, $GF(p)$ is the Galois Field of order $p$, which means you should be interpreting the coefficients modulo $p$. Also, $(x+1)^2$ isn't irreducible over any field, since $x+1$ will always be a factor. – user172541 Oct 29 '14 at 22:33

If you multiply $(x+1)^2$ and $x^3+x+1$ you get $x^5+2 x^3+x^2+x+1$, and if you multiply $x+1$ and $x^4+2x^3+x^2+1$ you get $x^5+3x^4+3x^3+x^2+x+1$. You don't get $x^5+x^2+x+1$. So what's happening here?
The Galois field $GF(p)$ for a prime $p$ is the integers modulo $p$. When you factor a polynomial over $GF(p)$, you regard the coefficients as integers modulo $p$. This is why $x^5+2x^3+x^2+x+1 = x^5+x^2+x+1$ in the first case, and $x^5+3x^4+3x^3+x^2+x+1 = x^5+x^2+x+1$ in the second case. As you can see, the factorization depends on $p$.
There is also a definition of $GF(q)$ for prime powers $q$, but you can ignore it for now.