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

  • 2
    $\begingroup$ I'm not quite sure what good it will be to calculate them, as there are 143.522.117. See oeis.org/… $\endgroup$ – Dr. belisarius Nov 12 '13 at 4:08
  • $\begingroup$ 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. $\endgroup$ – 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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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