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

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

• I'm not quite sure what good it will be to calculate them, as there are 143.522.117. See oeis.org/… – Dr. belisarius Nov 12 '13 at 4:08
• Over R none will be irreducible. Over Q would be a different matter. Over Z_2 there will be a large number of them, as @belisarius has already indicated. – Daniel Lichtblau Nov 12 '13 at 16:15

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]];
]
` 