0
$\begingroup$

I have a polynomial: $x^6 + x^4 + x^3 + x + 1$, and I need to factor it over $\mathbb{F}_2$, $\mathbb{F}_4$ and $\mathbb{F}_{16}$. I need to do it manually.

I wasn't even able to factor it over $\mathbb{F}_2$. I found a list of all irreducible polynomials of degree $\leqslant 5$ (here) and tried to divide the original polynomial by each of those, but with each one of them I got a remainder not equal to 0. So I either made a mistake with division or with the way I tried to solved this problem.

I have tried to read about various factorization algorithms, such as Berlekamp's algorithm, but they seem overcomplicated for this particular problem. I think there should be an easier approach to this problem.

In general, how to I try to come up with the factors? How do I know which polynomials are irreducible and which irreducible polynomials should I "look for" in my given polynomial?

$\endgroup$
  • $\begingroup$ You've already factored it over GF(2); it's irreducible. $\endgroup$ – Parcly Taxel May 25 '17 at 13:26
0
$\begingroup$

One very useful fact when dealing with polynomials over finite fields, is that all irreducible polynomials over $F_p$ of degree $r$ divide the polynomial $x^{p^r} - x$; and all other irreducible factors of that polynomial have a degree dividing $r$. While this takes some time to apply when $r$ is large, it gives you a way to know how many irreducible polynomials of degree $r$ there are, which is useful since most of the times you can find some irreducile polynomials by hand. This is particularly easy when $r$ is prime: in this case, all factors of $x^{p^r} - x$ of degree different than $r$ are those of degree one, and there are exactly $p$ of them: one for each root (every element of $F_p$ is a root). So the polynomial has $\frac{p^r - p}{r}$ irreducible factors of degree $r$, and these are actually all the polynomials of degree $r$ over $F_p$. I hope this helps!

$\endgroup$

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.