Sortie d'un élément primitif pour chaque taille de champ

16

Un élément primitif d'un champ fini est un générateur du groupe multiplicatif du champ. En d'autres termes, alphain F(q)est appelé élément primitif s'il est une q−1racine primitive de l'unité dans F(q). Cela signifie que tous les éléments non nuls de F(q)peuvent être écrits comme alpha^ipour un entier (positif) i.

Tous les éléments du champ F_{2^k}peuvent être écrits sous forme de polynômes de degré au plus k-1avec des coefficients qui sont soit 1ou 0. Pour que cela soit complet, votre code doit également générer un polynôme irréductible de degré kqui définit le champ que vous utilisez.

La tâche consiste à écrire du code qui génère un élément primitif F_{2^k}de votre choix pour chacun k = 1 .. 32dans l'ordre.

Votre sortie doit simplement lister les kcoefficients de l'élément primitif dans n'importe quel format que vous aimez, puis sur une ligne séparée les k+1éléments du polynôme irréductible. Veuillez séparer les sorties pour chaque valeur de ksi possible.

Votre code peut prendre autant de temps que vous le souhaitez, mais vous devez l'avoir exécuté jusqu'à la fin avant de soumettre votre réponse.

Vous ne pouvez pas utiliser de fonction intégrée ou de bibliothèque qui renvoie des éléments primitifs d'un champ fini ou teste si un élément est primitif.

Un exemple

Car k = 1le seul élément primitif est 1.

Car k = 2nous l'avons F_4. Les 4 éléments sont {0, 1, x, x + 1}donc il y a deux éléments primitifs xet x + 1. Ainsi, le code pourrait sortir

1 1
1 1 1

comme les coefficients par exemple où la deuxième ligne est le polynôme irréductible qui dans ce cas est celui x^2+x+1qui a des coefficients 1 1 1.


la source
4
Vous avez des exemples?
Okx
1
Pouvons-nous également produire les polynômes et / ou les éléments de champ codés comme les bits d'un entier que nous générons?
orlp
@orlp Oui absolument.
1
Je pense que Pari / GP est le seul langage qui a une fonction intégrée pour cela .
alephalpha
1
@Lembik OK. Essayez-le en ligne!
alephalpha

Réponses:

4

Mathematica, 127 octets

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

Explication:

Xn2n-1X2n-1-1Xje-1je2n-1

Production:

8589934581111111111111111111111111111110101

X32+X31+X30+X29+X28+X27+X26+X25+X24+X23+X22+X21+X20+X19+X18+X17+X16+X15+X14+X13+X12+X11+Xdix+X9+X8+Xsept+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
la source
C'est sympa. J'attends la version Jelly avec impatience :)