Mathematica Stack Exchange is a question and answer site for users of Mathematica. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
I'm not quite sure what good it will be to calculate them, as there are 143.522.117. See… – 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

Mathematica graphics

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:

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

Mathematica graphics

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.