Geben Sie für jede Feldgröße ein primitives Element aus

16

Ein primitives Element eines endlichen Feldes ist ein Generator der multiplikativen Gruppe des Feldes. Mit anderen Worten, alphain F(q)wird ein primitives Element genannt, wenn es eine primitive q−1Wurzel der Einheit in ist F(q). Dies bedeutet, dass alle Nicht-Null-Elemente von F(q)wie alpha^ifür eine (positive) Ganzzahl geschrieben werden können i.

Alle Elemente des Feldes F_{2^k}können als Polynome von höchstens Grad k-1mit Koeffizienten geschrieben werden, die entweder 1oder sind 0. Um dies vollständig zu machen, Ihr Code muss auch ein zur Ausgabe irreduzibles Polynom vom Grad , kdie das Feld definieren Sie verwenden.

Die Aufgabe besteht darin, Code zu schreiben, der in der angegebenen Reihenfolge ein primitives Element F_{2^k}Ihrer Wahl ausgibt k = 1 .. 32.

Ihre Ausgabe muss einfach die kKoeffizienten des primitiven Elements in einem beliebigen Format auflisten und dann in einer separaten Zeile die k+1Elemente des irreduziblen Polynoms. Bitte trennen Sie die Ausgänge nach kMöglichkeit für jeden Wert von .

Ihr Code kann so lange dauern, wie Sie möchten, aber Sie müssen ihn vollständig ausgeführt haben, bevor Sie Ihre Antwort senden können.

Sie dürfen keine eingebaute oder Bibliotheksfunktion verwenden, die primitive Elemente eines endlichen Feldes zurückgibt oder testet, ob ein Element primitiv ist.

Ein Beispiel

Denn k = 1das einzige primitive Element ist 1.

Denn k = 2wir haben F_4. Die 4 Elemente sind {0, 1, x, x + 1}also zwei primitive Elemente xund x + 1. So könnte der Code ausgeben

1 1
1 1 1

B. die Koeffizienten, bei denen die zweite Linie das irreduzible Polynom ist, das in diesem Fall x^2+x+1die Koeffizienten aufweist 1 1 1.


quelle
4
Hast du Beispiele?
Okx
1
Dürfen wir auch die Polynome und / oder Feldelemente ausgeben, die als Bits einer von uns ausgegebenen Ganzzahl codiert sind?
Orlp
@orlp Ja unbedingt.
1
Ich denke, dass Pari / GP die einzige Sprache ist , in der dies integriert ist .
Alephalpha
1
@Lembik OK. Probieren Sie es online!
Alephalpha

Antworten:

4

Mathematica, 127 Bytes

Do[For[i=2*2^n,PolynomialMod[x^Divisors[2^n-1]+1,i~IntegerDigits~2~FromDigits~x,Modulus->2]~Count~0!=1,i--];Print@{2,i},{n,32}]

Erläuterung:

xn2n-1x2n-1-1xich-1ich2n-1

Ausgabe:

8589934581111111111111111111111111111110101

x32+x31+x30+x29+x28+x27+x26+x25+x24+x23+x22+x21+x20+x19+x18+x17+x16+x15+x14+x13+x12+x11+x10+x9+x8+x7+x6+x5+x4+x2+1

{2,3}

{2,7}

{2,13}

{2,25}

{2,61}

{2.115}

{2,253}

{2.501}

{2,1019}

{2.2041}

{2.4073}

{2,8137}

{2,16381}

{2,32743}

{2,65533}

{2,131053}

{2,262127}

{2,524263}

{2,1048531}

{2,2097145}

{2,4194227}

{2,8388589}

{2,16777213}

{2,33554351}

{2,67108849}

{2,134217697}

{2,268435427}

{2,536870805}

{2,1073741801}

{2,2147483533}

{2,4294967287}

{2,8589934581}
Alephalpha
quelle
Das ist nett. Ich freue mich auf die Jelly-Version :)