Выведите примитивный элемент для каждого размера поля

16

Примитивный элемент конечного поля является образующей мультипликативной группы поля. Другими словами, alphain F(q)называется примитивным элементом, если он является примитивным q−1корнем единства в F(q). Это означает, что все ненулевые элементы F(q)можно записать как alpha^iдля некоторого (положительного) целого числа i.

Все элементы поля F_{2^k}могут быть записаны как полиномы степени не более k-1с коэффициентами, которые либо 1или 0. Чтобы завершить это, вашему коду также нужно вывести неприводимый многочлен степени, kкоторый определяет поле, которое вы используете.

Задача состоит в том, чтобы написать код, который выводит примитивный элемент F_{2^k}по вашему выбору для каждого k = 1 .. 32в порядке.

Ваш вывод должен просто перечислить kкоэффициенты примитивного элемента в любом формате, который вам нравится, а затем в отдельной строке k+1элементы неприводимого полинома. Пожалуйста, разделите выходы для каждого значения, kесли это возможно.

Ваш код может занять столько времени, сколько вы хотите, но вы должны выполнить его до завершения, прежде чем отправлять свой ответ.

Вы не можете использовать любую встроенную или библиотечную функцию, которая возвращает примитивные элементы конечного поля или проверяет, является ли элемент примитивным.

Пример

Для k = 1единственного примитивного элемента есть 1.

Ибо k = 2у нас есть F_4. 4 элемента, {0, 1, x, x + 1}так что есть два примитивных элемента xи x + 1. Таким образом, код может выводить

1 1
1 1 1

в качестве коэффициентов, например, где вторая строка является неприводимым многочленом, который в данном случае x^2+x+1имеет коэффициенты 1 1 1.


источник
4
Есть примеры?
Okx
1
Можем ли мы также вывести полиномы и / или элементы поля, закодированные как биты целого числа, которое мы выводим?
orlp
@orlp Да, конечно.
1
Я думаю, что Pari / GP - единственный язык, который имеет встроенный для этого .
алефальфа
1
@Lembik ОК. Попробуйте онлайн!
алефальфа

Ответы:

2

Пари / ГП , 114 байт

Вдохновлен ответом Исаака на другой вопрос.

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

Попробуйте онлайн!


Если встроенные модули разрешены:

Пари / GP , 61 байт (не конкурирует)

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

Попробуйте онлайн!

alephalpha
источник
4

Mathematica, 127 байт

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

Объяснение:

ИксN2N-1Икс2N-1-1Икся-1я2N-1

Выход:

8589934581111111111111111111111111111110101

Икс32+Икс+31+Икс30+Икс29+Икс28+Икс27+Икс26+Икс25+Икс24+Икс23+Икс22+Икс21+Икс20+Икс19+Икс18+Икс17+Икс16+Икс15+Икс14+Икс13+Икс12+Икс11+Икс10+Икс9+Икс8+Икс7+Икс6+Икс5+Икс4+Икс2+1

{2,3}

{} 2,7

{2,13}

{} 2,25

{2,61}

{2115}

{2253}

{2501}

{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
источник
Это приятно. Я с нетерпением жду версию Jelly :)