26
$\begingroup$

With primitive polynomials, it's not too hard to get all the polynomials of a particular power. For example, columns in the following represent the 18, 16, 48, and 60 primitive polynomials of GF[2^7], GF[2^8], GF[2^9], and GF[2^10]:

cavern 7

The Primitive Cavern

Cavern 9

Cavern 10

You can also enter at the left, visit every white space, and exit at the right. It's a continuous connected cavern.

But here, I got lost in the caverns of GF[2^12]. I wasn't able to visit all the white spaces, and likely got eaten by a grue. Is there an optimal way to shuffle this set of primitive polynomial coefficients?

Eaten by a grue

Here's more bad, dangerous caverns for all the primitive polynomials in caverns for powers 5 to 14.

dangerous caverns

Can the orderings of these primitive polynomials be made as safe as the solution for GF[2^7]-GF[2^10] at the top? Here are best found so for for GF[2^11] and GF[2^12]

Cavern 11

Cavern 12

$\endgroup$
5
  • 2
    $\begingroup$ Is the rotational symmetry in the three good patterns an accident? $\endgroup$
    – Ethan Bolker
    Commented Feb 10, 2017 at 18:14
  • $\begingroup$ Symmetry helps to simplify the problem. $\endgroup$
    – Ed Pegg
    Commented Feb 10, 2017 at 22:33
  • $\begingroup$ @EthanBolker: My guess would be that the rotational symmetry comes from the fact that the reciprocal of a primitive polynomial is always also primitive. The ordering of the columns may be such that the reciprocals appear at opposite ends. $\endgroup$
    – Jyrki Lahtonen
    Commented Feb 10, 2017 at 22:48
  • 1
    $\begingroup$ @EdPegg How do you computationally generate all the primitive polynomials for a given power ? Your caverns are very beautiful. $\endgroup$
    – Donald Splutterwit
    Commented Mar 31, 2017 at 0:58
  • $\begingroup$ Module[{prime = 2, pow = 12, div}, div = Reverse[Divisors[prime^pow - 1]]; Select[Total[ MapIndexed[ x^(#2[[1]] - 1) #1 &, #]] & /@ (Reverse[Flatten[{1, #}]] & /@ Tuples[Range[0, prime - 1], {pow}]), IrreduciblePolynomialQ[#, Modulus -> prime] && Length[ Union[Table[ PolynomialMod[x^div[[k]], #, Modulus -> prime], {k, 1, Length[div]}]]] == Length[div] &]] ----- This code will generate the primitive polynomials for GF[2^12]. $\endgroup$
    – Ed Pegg
    Commented Mar 31, 2017 at 14:54

1 Answer 1

Reset to default
5
$\begingroup$

A large bounty by Archmage Gruber prompted me to take another excursion into the caverns of the Galois Fields. It's said that some young fellow met his death in a duel amongst these grounds. Despite the obvious dangers, I delved in with new equipment. I wasn't able to improve GF[2^11] and GF[2^12] all that much, but at least I escaped unscathed at the other side. I should likely try giving up on symmetry, but it's hard to do that while traveling in a group.

GF 11

GF 12

I also ventured into GF[2^13] and GF[2^14]. It's difficult just to get to the other side with these caverns, but I spent a few days trying to make them safer. But I doubt that making them completely safe is possible.

GF 13

GF 14

Not the bounty of success that I had hoped for. But an interesting excursion, nevertheless.

UPDATE: GF[2^11] perfectly solved. Here are two solutions.

Galois Field 2^11 Galois Field 2^11

UPDATE 2: GF[2^12] almost perfectly solved.

Galois Field 2^12

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .