25
$\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$
  • 2
    $\begingroup$ Is the rotational symmetry in the three good patterns an accident? $\endgroup$ – Ethan Bolker Feb 10 '17 at 18:14
  • $\begingroup$ Symmetry helps to simplify the problem. $\endgroup$ – Ed Pegg Feb 10 '17 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 Feb 10 '17 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 Mar 31 '17 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 Mar 31 '17 at 14:54
4
$\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$

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.