Is there a way to find one irreducible polynomial of degree n in the field Z2

Question

I'm asked to find an irreducible polynomial of a certain degree in the field Z2.

I won't specify the degree I'm asked here because I'd like to understand the method and know how to apply it to later questions. I only need one irreducible polynomial, I don't need to find them all etc.

Assume that the degree is much too high to look for 2^n different polynomials, or to use polynomial long division to test against irreducible polynomials of degree < n+1/2

Your help and simple explanations would be greatly appreciated!

Edit: Okay thanks for your responses, they're very useful! It seems to get a direct answer I'll need to give the specific degree (however, if anyone could answer to solve with degree n that would be fantastic).

I need to find an irreducible polynomial of degree 20 in Z2. I have an idea but it seems very long-winded:

To find all of the irreducible polynomials of degree 5 then I need to find all the polynomials of degree 5 with no polynomial divisors of degree < 3.

Could I then repeat this to find the irreducible polynomials of degree 10 using the polynomials of degree 5 I found in the previous step, and then repeat again to find the irreducible polynomials of degree 20?

Like I said this seems very long winded, I'm sure there's an easier way.

Answer 1

In general it is difficult, but since testing irreducibility is reasonably fast (for a suitable definition of reasonably fast) finding one by random poking won't take too long because a random degree $n$ polynomial is irreducible with probability approximately $1/n$.

As Stella Biderman said, most methods are specific to the degree, and consequently ad hoc. Degree 20 you said? That is easy, because

• $20=\phi(25)$, and
• $2$ generates the group $\Bbb{Z}_{25}^*$.

These two facts together imply that the characteristic zero cyclotomic polynomial $$ \Phi_{25}(x)=\frac{x^{25}-1}{x^5-1}=x^{20}+x^{15}+x^{10}+x^5+1 $$ remains irreducible over $\Bbb{Z}_2$.

This is seen as follows. Let $\alpha$ be a primitive root of unity of order $25$ (in some extension field of $\Bbb{Z}_2$). Let $m(x)$ be the minimal polynomial of $\alpha$. By Galois theory we get all the zeros of $m(x)$ by repeatedly applying the Frobenius automorphism, $F:x\mapsto x^2$, to $\alpha$, so the zeros of $m(x)$ include $$ \alpha,\alpha^2,\alpha^4,\alpha^8,\alpha^{16},\alpha^{32}=\alpha^7, \alpha^{14},\ldots $$ By the second bullet above the list contains exactly the powers $\alpha^k, 1\le k<25, \gcd(k,25)=1$. In other words all the primitive roots of order $25$. Therefore $$ m(x)=\Phi_{25}(x) $$ is irreducible modulo two.

Answer 2

If $p(x)$ is is a prime polynomial, then it is an irreducible polynomial. If $p(x)$ is is a prime polynomial of degree $n$, then $\mathbb{Z}[x]/p(x)$ is a field of order $2^n$, and so $p(z)|z^{2^n}-z$. This will greatly narrow down the searching.

Most techniques rely on things specific to the exact degree unfortunately, and there is no useful general technique AFAIK.