Salida de un elemento primitivo para cada tamaño de campo

16

Un elemento primitivo de un campo finito es un generador del grupo multiplicativo del campo. En otras palabras, alphaen F(q)se llama un elemento primitivo si es una q−1raíz primitiva de la unidad en F(q). Esto significa que todos los elementos distintos de cero F(q)se pueden escribir como alpha^ipara algún entero (positivo) i.

Todos los elementos del campo F_{2^k}se pueden escribir como polinomios de grado como máximo k-1con coeficientes que son 1o 0. Para completar esto, su código también necesita generar un polinomio de grado irreduciblek que defina el campo que está utilizando.

La tarea es escribir código que genera un elemento primitivo F_{2^k}de su elección para cada uno k = 1 .. 32en orden.

Su salida simplemente debe enumerar los kcoeficientes del elemento primitivo en cualquier formato que desee y luego, en una línea separada, los k+1elementos del polinomio irreducible. Separe las salidas para cada valor de ksi es posible.

Su código puede demorar todo el tiempo que desee, pero debe haberlo ejecutado antes de enviar su respuesta.

No puede utilizar ninguna función incorporada o de biblioteca que devuelva elementos primitivos de un campo finito o pruebe si un elemento es primitivo.

Un ejemplo

Porque k = 1el único elemento primitivo es 1.

Para k = 2nosotros tenemos F_4. Los 4 elementos son {0, 1, x, x + 1}así que hay dos elementos primitivos xy x + 1. Entonces el código podría generar

1 1
1 1 1

como los coeficientes, por ejemplo, donde la segunda línea es el polinomio irreducible que en este caso es el x^2+x+1que tiene coeficientes 1 1 1.


fuente
44
¿Tienes algún ejemplo?
Okx
1
¿Podemos también generar los polinomios y / o elementos de campo codificados como los bits de un entero que generamos?
orlp 01 de
@orlp Sí, absolutamente.
1
Creo que Pari / GP es el único lenguaje que tiene incorporado esto .
alephalpha
1
@Lembik OK. Pruébalo en línea!
alephalpha

Respuestas:

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

Explicación:

Xnorte2norte-1X2norte-1-1Xyo-1yo2norte-1 .

Salida:

8589934581111111111111111111111111111110101

X32+X31+X30+X29+X28+X27+X26+X25+X24+X23+X22+X21+X20+X19+X18 años+X17+Xdieciséis+X15+X14+X13+X12+X11+X10+X9 9+X8+X7 7+X6 6+X5 5+X4 4+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
fuente
Esto es bonito. Espero con interés la versión Jelly :)