Как проверить многочлен на неприводимость

[Sender]

realeugene в сообщении #1245539 писал(а):

Сразу выкинуть все многочлены с чётным количеством ненулевых коэффициентов.

ТС уже догадался так сделать, судя по его следующему сообщению. Кстати, тут можно соорудить что-то вроде признака делимости Паскаля. Например, для проверки делимости многочлена $P(X)$ на $X^2+X+1$ можно разделить все его коэффициенты на $3$ группы, номера коэффициентов в каждой из которых дают одинаковые остатки при делении на $3$. Чтобы делимость $P(X)$ на $X^2+X+1$ имела место, необходимо и достаточно, чтобы суммы коэффициентов во всех группах были одинаковы в $\mathbb{Z}_2$.

Кстати, то, что в приведённых примерах циклическая перестановка коэффициентов неприводимого многочлена вновь даёт неприводимый многочлен, - случайность?

[realeugene]

Brukvalub в сообщении #1245344 писал(а):

Судя по тому, что, например, во втором томе Лидла и Нидеррайтера есть спец. таблицы неприводимых многочленов, регулярного способа все их найти нет.

Регулярный способ есть после обнаружения одного любого примитивного многочлена нужной степени.

-- 06.09.2017, 12:39 --

Sender в сообщении #1245545 писал(а):

Кстати, то, что в приведённых примерах циклическая перестановка коэффициентов неприводимого многочлена вновь даёт неприводимый многочлен, - случайность?

Случайность. Неслучайность то, что коэффициенты неприводимого многочлена, выписанные в обратном порядке, тоже дают неприводимый многочлен.

Sender в сообщении #1245545 писал(а):

Например, для проверки делимости многочлена $P(X)$ на $X^2+X+1$ можно разделить все его коэффициенты на $3$ группы, номера коэффициентов в каждой из которых дают одинаковые остатки при делении на $3$. Чтобы делимость $P(X)$ на $X^2+X+1$ имела место, необходимо и достаточно, чтобы суммы коэффициентов во всех группах были одинаковы в $\mathbb{Z}_2$.

Совершенно верно, так как любой неприводимый многочлен над GF(2) второго порядка делит $X^3+1$, можно сначала найти остаток от деления рассматриваемого многочлена на $X^3+1$, а потом исследовать делимость остатка на многочлен второго порядка.