Keluarkan elemen primitif untuk setiap ukuran bidang

16

Sebuah elemen primitif dari lapangan terbatas adalah generator dari kelompok perkalian dari lapangan. Dengan kata lain, alphain F(q)disebut elemen primitif jika itu adalah q−1akar persatuan primitif di Indonesia F(q). Ini berarti bahwa semua elemen non-nol F(q)dapat ditulis alpha^iuntuk bilangan bulat (positif) i.

Semua elemen bidang F_{2^k}dapat ditulis sebagai polinomial tingkat paling banyak k-1dengan koefisien yang salah 1atau 0. Untuk menyelesaikan ini, kode Anda juga perlu mengeluarkan polinomial derajat tak tereduksik yang menentukan bidang yang Anda gunakan.

Tugasnya adalah menulis kode yang menghasilkan elemen primitif yang F_{2^k}Anda pilih untuk masing-masing k = 1 .. 32secara berurutan.

Keluaran Anda hanya harus mencantumkan kkoefisien elemen primitif dalam format apa pun yang Anda suka dan kemudian pada baris terpisah k+1elemen polinomial yang tidak dapat direduksi. Silakan pisahkan output untuk setiap nilai kjika memungkinkan.

Kode Anda mungkin memakan waktu selama yang Anda inginkan, tetapi Anda harus menjalankannya sampai selesai sebelum mengirimkan jawaban Anda.

Anda tidak dapat menggunakan fungsi bawaan atau pustaka yang mengembalikan elemen primitif dari bidang hingga atau menguji apakah elemen tersebut primitif.

Sebuah contoh

Untuk k = 1satu-satunya elemen primitif adalah 1.

Untuk k = 2kita miliki F_4. Keempat elemen itu {0, 1, x, x + 1}jadi ada dua elemen primitif xdanx + 1 . Jadi kode bisa di-output

1 1
1 1 1

sebagai koefisien misalnya di mana baris kedua adalah polinomial yang tidak dapat direduksi yang dalam hal ini adalah x^2+x+1yang memiliki koefisien 1 1 1.


sumber
4
Punya contoh?
Okx
1
Bolehkah kita juga menampilkan polinomial dan / atau elemen bidang yang dikodekan sebagai bit integer yang kita hasilkan?
orlp
@ Atau ya benar-benar.
1
Saya pikir Pari / GP adalah satu-satunya bahasa yang memiliki built-in untuk ini .
alephalpha
1
@Lembik OK. Cobalah online!
alephalpha

Jawaban:

2

Pari / GP , 114 byte

Terinspirasi oleh jawaban isaacg dalam pertanyaan lain.

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)))

Cobalah online!


Jika built-in diizinkan:

Pari / GP , 61 byte (tidak bersaing)

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

Cobalah online!

alephalpha
sumber
4

Mathematica, 127 byte

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

Penjelasan:

xn2n1x2n11xi1i2n1

Keluaran:

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
sumber
This is nice. I look forward to the Jelly version :)