Two part question:

1) There are three irreducible cubic polynomials $\mathbb F_2$

Aproach: Bruteforce, there are not as much cubic polynomials, just 8 of them:

$x^3$

$x^3+1$

$x^3+x$

$x^3+x+1$

$x^3+x^2$

$x^3+x^2+1$

$x^3+x^2+x$

$x^3+x^2+x+1$

Only three of them are irreducible(??): $x^3+1$,$x^3+x+1$ and $x^3+x^2+1$

Reality check - do i miss point of irreducible polynomial here, and should consider adding $x^3+x^2+x+1$ to irreducible list? It is reducible, bit different way then other polynomials: $x^3+x^2+x+1=(x+1)^3$

2) Only irreducible polynomial of degree 2 over $\mathbb F_2$ is $x^2+x+1$. Does it help, with conjuction of part 1, to find all irreducible polynomials of degree 5?

up vote 2 down vote accepted

A polynomial in a field of degree two or three is irreducible if and only if it has no root. In $\mathbb F_2$ it is quite easy to check if a polynomial has a root:

  1. $0$ should be no root $\Leftrightarrow$ the constant coefficient is $1$.
  2. $1$ should be no root $\Leftrightarrow$ the number of non-zero coefficients is odd.

Both conditions can only be satisfied for non-constant polynomials if we have at least three non-zero coefficients. Five coefficients is too much for a polynomial of degree at most three. So we are looking for the polynomials with exactly three non-zero coefficients which are

  1. $x^2+x+1$,
  2. $x^3+x^2+1$,
  3. $x^3+x+1$.

In particular your polynomial $x^3+1$ is reducible since $1$ is a root.

Interesting side note:

Let $p,q$ be primes. It is quite easy to determine the number of irreducible polynomials in $\mathbb F_p[x]$ of degree $q$. Because each element in $\mathbb F_{p^q}\setminus \mathbb F_p$ is of degree $q$ and every irreducible polynomial of degree $q$ with leading coefficient $1$ is the minimal polynomial of exactly $q$ elements in $\mathbb F_{p^q}\setminus \mathbb F_p$ we get that the number of irreducible polynomials in $\mathbb F_p[x]$ of degree $q$ with leading coefficient $1$ is $$\frac{p^q-p}{q}.$$

So the total number of irreducible polynomials in $\mathbb F_p[x]$ of degree $q$ is $$\frac{(p^q-p)(p-1)}{q}$$ because we can multiply each of the former polynomials with one of the $p-1$ many units of $\mathbb F_p$.

Application:

Using this result we get for $p=2$ and $q=2,3,5$ that there are $$\frac{2^q-2}{q} = 1,2,6$$ irreducible polynomials of degree $q$ in $\mathbb F_2[x]$ which answers the question.

  • this is great info, thanks what about reducibility of degree 5? – Timo Junolainen Sep 3 '15 at 13:20
  • @TimoJunolainen See my edit. – principal-ideal-domain Sep 3 '15 at 13:25
  • thanks a lot! feeling little fuzzy on subject, this clears a lot of things up – Timo Junolainen Sep 3 '15 at 13:35

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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