How can I get a irreducible polynomial of degree 8 over $Z_2[X]$?

Question

I have got one of degree 5: $x^5+x^2+1$, but I need one of degree 8.

Answer 1

The only way I know is trial and error. A polynomial of degree $8$ is irreducible/prime over $\mathbb Z_2$ if it divides:

$$\frac{x^{2^8}-x}{x^{2^4}-x}=\frac{x^{255}-1}{x^{15}-1} = 1+x^{15}+x^{30}+\cdots x^{225}+x^{240}$$

This polynomial is exactly the product of all the prime polynomials of degree $8$, once each.

It's probably easier to use repeated squaring to prove that $p(x)$ divides $x^{256}-x$ and not $x^{16}-x$.

This means there are $30$ such polynomials. Since we want an eighth-degree polynomial, and it is not divisible by $x$ or $x-1=x+1$, this means:

$$p(x)=1+\cdots + x^8$$ where the number of terms in $\cdots$ is odd. So there are $\frac{2^7}{2}=64$ subsets of $\{1,2,\dots,7\}$ that are odd, and therefore, if you chose your $p(x)$ at random under these conditions, you'd get approximately $50\%$ chance of finding a prime each trial.

You can remove the cases where the subset of $\{1,\dots,7\}$ are only even. For example, we know: $$1+x^4+x^6+x^8 = (1+x^2+x^3+x^4)^2$$ That process removes $4$ of the $64$ bad options, and now we have exactly a $50\%$ chance.

We can also avoid duplicate testing by not testing reflections. Assuming $a_0=a_8=1$, then $\sum_0^8 a_ix^i$ is irreducible if and only if $\sum_{0}^8 a_{8-i}x^i$ is irreducible.

So if you've eliminated $1+x+x^8$, you've eliminated $1+x^7+x^8$, for example.

That doesn't reduce our options quite in half, because some polynomials are self-reflective. (And it doesn't increase our initial odds of finding a prime on the first try.)

This still requires trial and error.

Example trial for $p(x)=1+x+x^8$. Then:

$$x^{8}\equiv 1+x\pmod{p(x)}\\ x^{16}\equiv 1+x^2\pmod{p(x)}$$ So $x^{16}-x$ is not divisible by $p(x)$. $$x^{32}\equiv 1+x^4\pmod{p(x)}\\ x^{64}\equiv 1+x^8\equiv x\pmod{p(x)}\\ x^{128}\equiv x^2\pmod{p(x)}\\ x^{256}\equiv x^4\pmod{p(x)}$$

We could actually stop at $x^{64}$, since it means that $p(x)$ divides $x^{2^6}-x$, which means it must be the product of primes of degree $1,2,3,$ and $6$. Since it is not divisible by a linear polynomial it must be divisible by the only prime of degree $2$, $q(x)=1+x+x^2$. Since $(1+x+x^2)(1+x)=x^3+1$, we get that:

$$p(x)\equiv 1+x+x^5\equiv 1+x+x^2\pmod{1+x+x^2}$$ Indeed, this gives us another way to ensure that $p(x)$ is not prime: $1+x+x^2$ divides $\sum a_ix^i$ with $\sum a_i=1$ and $a_0=a_8=1$ if $$a_3+a_6=0, a_1+a_4+a_7=1\\a_2+a_5=0$$

We get that $1+x^3+x^8$ is divisible by $1+x+x^3$.

I get that $1+x+x^2+x^4+x^8$ is prime, but I'd want to check this.

Another way to check, by the way, is to ensure that $p(x)$ is relatively prime to $x^{8}-x$ (and thus not divisible by any prime of degree $3$) and relatively prime to $x^{16}-x$, and thus not divisible by any prime of degree $1,2,4$.

I get that $1+x+x^3+x^4+x^8$ is irreducible, but I did it on paper, so I'd want to check.