Как запрограммировать построение мультипликативной группы по неприводимому многочлену?

Question

[fanihab442]

Мне нужно запрограммировать построение мультипликативной группы по неприводимому многочлену, но я не знаю алгоритма, по которому это можно сделать.

Пример входных данных:
2 4
1 0 0 1
Соответствующие выходные данные:
0 0 0 1
0 0 1 0
0 1 0 0
1 0 0 0
0 0 1 1
0 1 1 0
1 1 0 0
1 0 1 1
0 1 0 1
1 0 1 0
0 1 1 1
1 1 1 0
1 1 1 1
1 1 0 1
1 0 0 1

Answer 1

[Wataru]

Научитесь выполнять операции в группе. Перемножение полиномов происходит как обычно, двумя циклами, но надо потом взять по модулю многочлена, образующего группу. Тут надо будет реализовать деление столбиком.

А дальше, чтобы найти мультипликативную группу, придется делать полный перебор. Перебирайте все полиномы (они у вас, видимо, над полем по модулю 2, их 2^n. Можно их перебирать как биты у целого числа). Потом умножайте на текущий полином в цикле, помечая в массиве уже полученные ранее полиномы. Если получили все 2^n элементов - вы нашли нужную группу. Если наткнулись на уже ранее полученный полином раньше времени - текущий кандидат не подходит.

Answer 2

[Sumor]

Биты в мультипликативных группах означают коэффициенты при соответствующих членах многочлена.
Судя по всему 1001 означает неприводимый многочлен: 1*x^4+0*x^3+0*x^2+1*x^1+1 = x^4+x+1
По свойствам таких групп достаточно взять любой элемент, кроме единицы и нуля, и его степени дадут вам все элементы.
Проще всего взять элемент x, который соответствует числу 0010. Перебираем все его степени - получаем все элементы и таблицу умножения. Помним что у нас 1+1 = 0 и плюс равен минусу.
x^0 = 1 = 0001
x^1 = x = 0010
x^2 = 0100
x^3 = 1000
x^4 - этот элемент больше нашего многочлена - нужно найти остаток от деления:
x^4 : (x^4+x+1) = 1 * (x^4+x+1) + x+1 - остаток x+1 = 0011
x^5 = x^4 * x = (x+1)*x= x^2 + x = 0110
x^6 = x^5 * x = (x^2 + x)*x = x^3 + x^2 = 1100
x^7 = x^6 * x = (x^3 + x^2)*x= x^4+x^3 - опять получили больше нашего многочлена - находим остаток от деления
(x^4+x^3): (x^4+x+1) = 1 * (x^4+x+1) + x^3+x+1 = 1011
и продолжаем до x^14

Comments

[Wataru]

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

Неправда.

Если для вашего многочлена x является генератором, то x^3 им точно не является. Потому что в мультипликативной группе должно быть 15 элементов. Если взять x^3 то оно сгенерирует x^6, x^9, x^12, x^15 = 1. Только 5 элементов.

Это так всегда, если мощность группы не простое число.

[Sumor]

Согласен, слегка поторопился.