Generating irreducible polynomials for binary numbers

Question

From a paper, there is a discussion about generating irreducible polynomials for a certain degree as can be seen below.

The reference is wolfram, but it is not clear how those polynomials are generated. For example, 37 and 41 are shown below.

     5 4 3 2 1 0
37 = 1 0 0 1 0 1  (x5+x2+1)
41 = 1 0 1 0 0 1  (x5+x3+1)

With this tool, I can verify that x5+x2+1 is irreducible. But how those numbers are generated is a question for me. Unfortunately, the author didn't answer that. I would like to generate other degrees, e.g. 6 or 7.

Any help on that?

Answer 1

For small degrees you can basically do this by hand with a variant of the sieve of Eratosthenes, starting with all polynomials and then successively eliminating those that are divisible by polynomials of lower degree. For polynomials of degree $6$ it suffices to eliminate polynomials which are divisible by irreducible polynomials of degree $\le 3$. These are easy to list: $x, x + 1, x^2 + x + 1, x^3 + x + 1, x^3 + x^2 + 1$. To check our work we can use the fact that there are

$$\frac{1}{n} \sum_{d \mid n} \mu(d) 2^{\frac{n}{d}}$$

monic irreducible polynomials of degree $n$ over $\mathbb{F}_2$, which handily reduces to $\frac{2^p - 2}{p}$ when $n = p$ is prime. So there is $\frac{2^2 - 2}{2} = 1$ irreducible of degree $2$ and $\frac{2^3 - 2}{3} = 2$ irreducibles of degree $3$, which we've listed. You can check that the cubic polynomials are irreducible by verifying that they have no linear factors, which just means they have to end in $1$ (to not be divisible by $x$) and have an odd number of terms (to not be divisible by $x + 1$).

So, there are $2^6 = 64$ monic polynomials of degree $6$. Of these, half do not end with $1$ so are divisible by $x$ and we can eliminate them, giving $2^5 = 32$ monic polynomials of degree $6$ ending with $1$. Of these, half have an even number of terms so are divisible by $x + 1$ and we can eliminate them too, giving $2^4 = 16$ monic polynomials of degree $6$ ending with $1$ with an odd number of terms as our remaining candidates. Via the necklace formula above we know that there are

$$\frac{2^6 - 2^3 - 2^2 + 2}{6} = 9$$

monic irreducibles of degree $6$, so we have to eliminate $7$ of the remaining candidates. Testing for divisibility by $x^2 + x + 1$ is easy because $x^3 \equiv 1 \bmod (x^2 + x + 1)$ so we can reduce exponents $\bmod 3$. This eliminates the following $4$ polynomials:

$$x^6 + x^3 + x^2 + x + 1 \equiv x^2 + x + 1 \bmod x^2 + x + 1$$ $$x^6 + x^4 + x^3 + x^2 + 1 \equiv x^2 + x + 1 \bmod x^2 + x + 1$$ $$x^6 + x^5 + x^4 + x^3 + 1 \equiv x^2 + x + 1 \bmod x^2 + x + 1$$ $$x^6 + x^5 + x^3 + x + 1 \equiv x^2 + x + 1 \bmod x^2 + x + 1.$$

The condition these polynomials satisfy is that the exponents which occur in the middle, between $x^6$ and $1$, are in arithmetic progression; that's easy enough to remember. The only polynomials left to eliminate after this are ones which have only irreducible cubic factors. There are $3$ of these and we can just compute them:

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

The remaining $9$ polynomials are all irreducible. Here they are:

$$\boxed{ \begin{eqnarray*} x^6 + x + 1 &=& \text{Poly}(67) \\ x^6 + x^3 + 1 &=& \text{Poly}(73) \\ x^6 + x^4 + x^2 + x + 1 &=& \text{Poly}(87) \\ x^6 + x^4 + x^3 + x + 1 &=& \text{Poly}(91) \\ x^6 + x^5 + 1 &=& \text{Poly}(97) \\ x^6 + x^5 + x^2 + x + 1 &=& \text{Poly}(103) \\ x^6 + x^5 + x^3 + x^2 + 1 &=& \text{Poly}(109) \\ x^6 + x^5 + x^4 + x + 1 &=& \text{Poly}(115) \\ x^6 + x^5 + x^4 + x^2 + 1 &=& \text{Poly}(117) \end{eqnarray*} }$$

which you can confirm via the OEIS. It may also be a bit easier and more enlightening to do this computation by writing everything in terms of binary strings.

Answer 2

But how those numbers are generated is a question for me [...] I would like to generate other degrees, e.g. 6 or 7.

Pick a polynimial $p(x)$ of degree $d$ in $\Bbb F_2[x]$ at random and then check whether it's irreducible. In order for this to be the case:

1. If the polynomial shall have degree $d$, then $a_d=1$ where $a_k$ is the coefficient at $x^k$.

2. It must be that $a_0=1$, because otherwise $x\mid p(x)$ resp. $0$ is a zero of $p$.

3. The number of non-zero coefficients must be odd, because otherwise $p(1) = 0$, i.e. $x+1 \mid p(x)$.

This leaves you with a total $2^{d-2}$ possible polynomials from which to pick. In some applications it is preferred that the popcount (numner of non-zero coefficients) is small, so you's start with a popcount of 3, then 5, then 7, etc.

In order to check whether the polynomial is actually irreducible, notice that

$$\Bbb F_2[x] / p(x)\text{ is a field}\quad\iff\quad p(x)\text{ is irreducible over } \Bbb F_2$$

In the case when $p$ is irreducible, the field is $$\Bbb F_{2^d}\simeq \Bbb F_2[x] / p(x)$$

and the group of units $\Bbb F_{2^d}^\times$ is cyclic of order $2^d-1$. We can show irreducibility of $p$ by finding a generator $a$ of $\Bbb F_q^\times$, $q := 2^d$:

1. Pick some element $a\neq 0$ in $\Bbb F_2[x]/p(x)$.

2. If $a^{q-1}\neq 1$ then $p$ is not irreducible.

3. If $a^{(q-1)/k}\neq 1$ for all prime divisors $k\mid(q-1)$ then $a$ generates $\Bbb F_q^\times$ and $p$ is irreducible. Otherwise, goto 1. because $a$ is not a generator.

All this works well enough in practive because there are "enough" irreducible polynomials, and there are "enough" primitive roots $a$. This means the "pick at random" parts have a high chance of being lucky. the hardest part is that for step 3. you'll have to know the factorization of $2^d-1$.

All this carries over exactly the same for other characteristics other than $2$.