Prymitywny elementu skończonego pola jest generatorem multiplikatywna grupa pola. Innymi słowy, alphain F(q)jest nazywany prymitywnym elementem, jeśli jest prymitywnym q−1korzeniem jedności w F(q). Oznacza to, że wszystkie niezerowe elementy F(q)mogą być zapisane jak alpha^idla niektórych (dodatnich) liczb całkowitych i.

Wszystkie elementy tej dziedzinie F_{2^k}mogą być zapisywane jako wielomianów stopnia co najwyżej k-1ze współczynnikami, które są albo 1albo 0. Aby to zakończyć, twój kod musi również wygenerować nieredukowalny wielomian stopnia, kktóry określa pole, którego używasz.

Zadanie polega na napisaniu kodu, który wyprowadza prymitywny element F_{2^k}wybrany dla każdego k = 1 .. 32w kolejności.

Twój wynik musi po prostu wyszczególnić kwspółczynniki pierwotnego elementu w dowolnym formacie, który ci się podoba, a następnie w osobnym wierszu k+1elementy nieredukowalnego wielomianu. Proszę oddzielić wyjścia dla każdej wartości, kjeśli to możliwe.

Twój kod może trwać tak długo, jak chcesz, ale musisz przesłać go do końca przed przesłaniem odpowiedzi.

Nie możesz używać żadnej funkcji wbudowanej lub biblioteki, która zwraca prymitywne elementy pola skończonego lub testuje, czy element jest prymitywny.

Przykład

Bo k = 1jedynym prymitywnym elementem jest 1.

Ponieważ k = 2mamy F_4. 4 elementy są {0, 1, x, x + 1}więc są dwa prymitywne elementy xi x + 1. Aby kod mógł zostać wygenerowany

1 1
1 1 1

jako współczynniki, na przykład gdy druga linia jest nieredukowalnym wielomianem, który w tym przypadku x^2+x+1ma współczynniki 1 1 1.

Pari / GP , 114 bajtów

Zainspirowany przez Isaacga na inne pytanie.

for(n=1,32,for(i=1,2^n,if(sumdiv(2^n-1,d,Mod(x,f=Mod(Pol(binary(2*2^n-i)),2))^d==1)==1,print([x,lift(f)]);break)))

Wypróbuj online!

---

Jeśli wbudowane są dozwolone:

Pari / GP , 61 bajtów (niekonkurencyjne)

for(i=1,32,print([ffprimroot(ffgen(f=ffinit(2,i))),lift(f)]))

Wypróbuj online!

Mathematica, 127 bajtów

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

Wyjaśnienie:

$x$$n$$2^n - 1$$x^{2^n - 1} - 1$$x^i - 1$$i$$2^n - 1$

Wynik:

$8589934581$$111111111111111111111111111110101$

$$x^{32}+x^{31}+x^{30}+x^{29}+x^{28}+x^{27}+x^{26}+x^{25}+\\x^{24}+x^{23}+x^{22}+x^{21}+x^{20}+x^{19}+x^{18}+x^{17}+\\x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^9+\\x^8+x^7+x^6+x^5+x^4+x^2+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}