Generating irreducible polynomials over $GF(2)$

Question

I just want a clear answer to generating all the irreducible polynomials upto a certain degree in GF(2) (in my case upto 16)

I am storing the prime polynomials as unsigned int

Answer 1

The idea to generate all irreducible polynomials over a finite field up to some degree $d$ is an induction process.

If $d=1$ all polynomials of degree $1$ are irreducible.

If $d>1$ then generate first all polynomials of degree $d$ (without even considering the problem of irreducibility). You have $2^d$ of them (if you work over $GF(2)$). Take $P$ one polynomial of degree $d$, if it is not irreducible then there exists $Q_1,Q_2$ of degree $>1$ and $<d$ such that $P=Q_1Q_2$. At least one of them is below $\frac{d}{2}$. Furthermore, up to the consideration of some divisors of $Q_1$, $Q_2$, we can even assume that $Q_1$ is irreducible and of degree below $\frac{d}{2}$.

Hence, in order to check whether $P$ is irreducible, it suffices to check if there exists an irreducible polynomial $Q$ of degree below $\frac{d}{2}$ dividing $P$. Since we already computed (by induction) the set of those irreducible polynomials, we can do this for every $Q$ irreducible of degree below $\frac{d}{2}$: if $Q$ divides $P$ for some $Q$ then $P$ has a divisor and $P$ isn't irreducible; if no $Q$ divides $P$ then $P$ is irreducible by what is written above. Doing this for every $P$ polynomial of degree $d$ we get the list of irreducible polynomials of degree $d$.