How can I calculate all irreducible polynomials of 31 degree in $\mathbb Z_2[x]$?

Question

How can I calculate all binary irreducible polynomials of degree 31? or how i calculate all irreducible $f$ in $\mathbb Z_2[x]$?

(The irreducible polynomial in $\mathbb Z_2[x]$ and $\mathbb R$ are distinguish; for example, in $\mathbb Z_2[x]$, we have $x^2+1=(x+1)(x+1)$.)

Answer 1

This gives you the irreducible polynomials up to order n - 1 in $\mathbb Z_2[x]$

n = 5; 
Table[Pick @@ Transpose[({#, IrreduciblePolynomialQ[#, Modulus -> 2]} & /@ 
                                       (FromDigits[#, x] & /@ Tuples[{0, 1}, i]))], 
      {i, n}] // Column

However, for degree 31 there are 2^32 == 4,294,967,296 tuples to explore. That's not feasible in this way.

I doubt about the usefulness of calculating them all, but here's a memory-diet way to do that given enough lifespan on your part:

Needs["Combinatorica`"];
s = {};
n = 31;
While[(s = NextSubset[Range[n + 1], s]) != {},
     If[IrreduciblePolynomialQ[#, Modulus -> 2], Print@#] &[
                   Array[x^# &, n + 1, 0].SparseArray[Thread[Rule[s, 1]], n + 1]];
 ]