1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user172541 Oct 29 '14 at 22:33
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That makes a lot more sense! Thanks! $\endgroup$ – Nelson.b.austin Oct 29 '14 at 22:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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