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.

This is what I tried:

It's evident that $x,x+1$ are irreducible. Then, use these to find all reducible polynomials of degree 2. There ones that can't be made are irreducible. Then use these to make polynomials of degree 3, the ones that can't be made are irreducible. Repeat until degree 5.

Doing this way takes way too long and I just gave up during when I was about to reach degree 4 polynomials.

My question is: is there any easier way to find these polynomials?

P.S.: this is not exactly homework, but a question which I came across while studying for an exam.

share|improve this question
    
A polynomial of degree $2$ or $3$ must have a linear factor. To show that linear functions $x$ and $x + 1$ are not factors of $p(x)$, it suffices to show that $p(0) \neq 0$ and $p(1) \neq 0$. For polynomials of degree $4$ and $5$, you need to check that it has no linear factor and no factor of degree $2$. Also, in your degree $4$ and $5$ calculations, you can rule out all polynomials $q(x)$ with $q(0) = 0$ or $q(1) = 0$, so you can at least rule out a few cases. –  JavaMan Apr 11 '11 at 1:24
    
Interesting. I was checking only for the factors, completely forgot about evaluating them at 0 and 1. That already helps quite a bit. Thought at degree 5 there are still too many polynomials to check, so my guess is there is some really clever way to check if a pol. is irreducible in this ring. –  Leonardo Fontoura Apr 11 '11 at 1:30
5  
There are $2^5 = 32$ polynomials of degree $5$. For a polynomial $p(x)$, note that the condition $p(0) \neq 0$ implies that $p(x) = x^5 + ax^4 + bx^3 + cx^2 + dx + 1$ (i.e., $p$ has nonzero constant term). The condition $p(1) \neq 0 $ implies that $p(x)$ has an odd number of terms. This already eliminates 24 of the 32 cases. I cannot, however, see a more clever way, although I'm also sure that one exists. –  JavaMan Apr 11 '11 at 1:39
    
@DJC Both your comments combined ended up being the most helpful (even thought both submited answers are good). So, if you would care to submit it as an answer, I'll accept it. Thank you. –  Leonardo Fontoura Apr 11 '11 at 18:09
add comment

3 Answers

up vote 7 down vote accepted

Extrapolated Comments converted to answer:

First, we note that there are $2^n$ polynomials in $\mathbb{Z}_2[x]$ of degree $n$.

A polynomial $p(x)$ of degree $2$ or $3$ is irreducible if and only if it does not have linear factors. Therefore, it suffices to show that $p(0) = p(1) = 1$. This quickly tells us that $x^2 + x + 1$ is the only irreducible polynomial of degree $2$. This also tells us that $x^3 + x^2 + 1$ and $x^3 + x + 1$ are the only irreducible polynomials of degree $3$.

As hardmath points out, for a polynomial $p(x)$ of degree $4$ or $5$ to be irreducible, it suffices to show that $p(x)$ has no linear or quadratic factors. To rule out the linear factors, we can again throw out any polynomial not satisfying $p(0) = p(1) = 1$. That is, we can throw out any polynomial with constant term $0$, and we can throw out any polynomial with an even number of terms. This rules out $3/4$ of the polynomials. For example, the $4^{th}$ degree polynomials which do not have linear factors are:

  • $ x^4 + x^3 + x^2 + x + 1 $
  • $ x^4 + x^3 + 1 $
  • $ x^4 + x^2 + 1 $
  • $ x^4 + x + 1 $

The $5^{th}$ degree polynomials which do not contain linear factors are:

  • $x^5 + x^4 + x^3 + x^2 + 1$
  • $x^5 + x^4 + x^3 + x + 1$
  • $x^5 + x^4 + x^2 + x + 1$
  • $x^5 + x^3 + x^2 + x + 1$
  • $x^5 + x^4 + 1$
  • $x^5 + x^3 + 1$
  • $x^5 + x^2 + 1$
  • $x^5 + x + 1$

It still remains to check whether $x^2 + x + 1$ (which is the only quadratic irreducible polynomial in $\mathbb{Z}_2[x]$) divides any of these polynomials. This can be done by hand for sufficiently small degrees. Again, as hardmath points out, since $x^2 + x + 1$ is the only irreducible polynomial of degree $2$, it follows that $(x^2 + x + 1)^2 = x^4 + x^2 + 1$ is the only polynomial of degree $4$ which does not have linear factors and yet is not irreducible. Therefore, the other $3$ polynomials listed must be irreducible. Similarly, for degree $5$ polynomials, we can rule out

$$ (x^2 + x + 1)(x^3 + x^2 + 1) = x^5 + x + 1 $$

and

$$ (x^2 + x + 1)(x^3 + x + 1) = x^5 + x^4 + 1. $$

The other $6$ listed polynomials must therefore be irreducible.

Notice that this trick of throwing out polynomials with linear factors, then quadratic factors, etc. (which hardmath called akin to the Sieve of Eratosthenes) is not efficient for large degree polynomials (even degree $6$ starts to be a problem, as a polynomial of degree $6$ can factor as a product of to polynomials of degree $3$). This method, therefore only works for sufficiently small degree polynomials.

To recap, the irreducible polynomials in $\mathbb{Z}_2[x]$ of degree $\leq 5$ are:

  • $x$
  • $x+1$
  • $x^2 + x + 1$
  • $x^3 + x^2 + 1$
  • $x^3 + x + 1$
  • $ x^4 + x^3 + x^2 + x + 1 $
  • $ x^4 + x^3 + 1 $
  • $ x^4 + x + 1 $
  • $x^5 + x^4 + x^3 + x^2 + 1$
  • $x^5 + x^4 + x^3 + x + 1$
  • $x^5 + x^4 + x^2 + x + 1$
  • $x^5 + x^3 + x^2 + x + 1$
  • $x^5 + x^3 + 1$
  • $x^5 + x^2 + 1$
share|improve this answer
    
Very good and concise answer. –  Leonardo Fontoura Apr 13 '11 at 3:15
    
Thanks! Credit should also go to @Hardmath for pointing out the bit about quadratics. –  JavaMan Apr 13 '11 at 3:17
add comment

The tricky way to do this is to realize that if $p(x)$ is prime polynomial of degree $n$, then ${\mathbb{Z}_2[z]}/{p(z)}$ is a field of order $2^n$ and hence for every element $a$ of the field, $\ a^{2^n}-a = 0$. In particular, then, $z^{2^n}-z$ must be divisible by $p(z)$. Now, $z^{2^n}-z$ is also divisible by any prime polynomial of degree $d|n$, so we first have to factor those out, and then you get the product of the primes of degree $n$.

In particular, $x^8-x$ must be a product of the primes of degree one and the primes of degree $3$. We can easily factor out $x(x+1),$ and we see that the primes of degree $3$ must multiply together to get $x^6+x^5+x^4+x^3+x^2+x+1$. So you can test for primeness of a polynomial of degree $3$ by seeing if it divides into this polynomial.

Similarly, for $n=4$, you have $x^{16}-x$ must be the product of the primes of degrees $1,2$ and $4$. The only prime of degree $2$ is $x^2+x+1,$ so the product of the primes of degree $4$ must be $\dfrac{x^{16}-x}{(x^2+x+1)x(x+1)}\ =\ 1 + x^3 + x^6 + x^9 + x^{12}\:.\ $ So we know that there are $3$ primes of order $4$.

Finally, the products of the primes of degree $5$ must be $\ \dfrac{x^{32}-x}{x(x+1)}\ =\ 1 + x + x^2 +\:\cdots\: + x^{30}$.

Not that the primes of degree $3$ have to be $x^3+x+1$ and $x^3+x^2+1$. That's because if $p(x)$ is prime, then $p(1)=1$ and $p(0)=1$. So we have to have $x^3$ and $1$ as terms f $p(x)$, and we have to have an odd number of non-zero terms in $p(x)$.

share|improve this answer
    
I'm not sure if I find this easier or not. ): –  Leonardo Fontoura Apr 11 '11 at 1:49
    
Yeah,this trick is really more useful for higher degrees. –  Thomas Andrews Apr 11 '11 at 1:54
add comment

As DJC points out, much of the spade work is noticing which polynomials have linear factors, or equivalently which have roots at 0 or 1. This is sufficient to check quadratic and cubic polynomials (mod 2).

The only other thing to rule out (in finding irreducible polynomials of degree 5 or less) is a quadratic factor! So by analogy with the Sieve of Eratosthenes, let's use the evaluation at 0 and 1 (constant term not 0 and number of nonzero coefficients odd) to quickly list all the irreducible polynomials (mod 2) of degree 2:

$x^2 + x + 1$

Then a polynomial (mod 2) of degree 4 or 5 is irreducible if and only if in addition to not having a root at x = 0 or x = 1, the polynomial does not have the one irreducible quadratic above as a factor. For degree 4 it is only possible to have the quadratic factor but no linear one if the polynomial is the quadratic irreducible squared, so that's just one case to check.

$(x^2 + x + 1)^2 = x^4 + x^2 + 1$
[reducible]

For degree 5 the analogous test would be to rule out the irreducible quadratic times one of the (two) irreducible cubic polynomials.

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.