7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Sometimes there are methods which work for certain degrees, and then the method only works based on same extra property your degree might have. $\endgroup$ – N. S. Mar 2 '16 at 17:36
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\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.