Saída de um elemento primitivo para cada tamanho de campo

16

Um elemento primitivo de um campo finito é um gerador do grupo multiplicativo do campo. Em outras palavras, alphain F(q)é chamado de elemento primitivo se for uma q−1raiz primitiva da unidade em F(q). Isso significa que todos os elementos diferentes de zero F(q)podem ser escritos como alpha^ipara algum número inteiro (positivo) i.

Todos os elementos do campo F_{2^k}podem ser escritos como polinômios de grau, no máximo, k-1com coeficientes que são 1ou 0. Para concluir isso, seu código também precisa gerar um polinômio irredutível de grau kque define o campo que você está usando.

A tarefa é escrever código que gera um elemento primitivo F_{2^k}de sua escolha para cada um k = 1 .. 32em ordem.

Sua saída deve simplesmente listar os kcoeficientes do elemento primitivo em qualquer formato que você desejar e, em uma linha separada, os k+1elementos do polinômio irredutível. Separe as saídas para cada valor, kse possível.

Seu código pode levar o tempo que você quiser, mas você deve executá-lo até concluir antes de enviar sua resposta.

Você não pode usar nenhuma função interna ou de biblioteca que retorne elementos primitivos de um campo finito ou teste se um elemento é primitivo.

Um exemplo

Pois k = 1o único elemento primitivo é 1.

Pois k = 2nós temos F_4. Os 4 elementos são {0, 1, x, x + 1}então existem dois elementos primitivos xe x + 1. Então o código pode gerar

1 1
1 1 1

como os coeficientes, por exemplo, onde a segunda linha é o polinômio irredutível que, neste caso, é o x^2+x+1que possui coeficientes 1 1 1.


fonte
4
Tem algum exemplo?
Okx 01/07/19
1
Também podemos produzir os polinômios e / ou elementos de campo codificados como os bits de um número inteiro que produzimos?
Ou orp
@orlp Sim, com certeza.
1
Eu acho que Pari / GP é a única linguagem que tem um built-in para isso .
Alephalpha
1
@Lembik OK. Experimente online!
Alephalpha

Respostas:

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

Explicação:

xn2n-1x2n-1-1xEu-1Eu2n-1

Resultado:

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}
alefalpha
fonte
Isso é legal. Estou ansioso para a versão Jelly :)