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

[student1138]

Добрый день. Стоит такая задача: выписать неприводимые многочлены над $\mathbb{Z}_2$ степеней 4 и 5.
Я придумал что можно например выписать все многочлены соответствующих степеней в первом случае их будет 16, во втором 32. Но затем нужно каждый из них проверить на неприводимость. Но как это сделать? Есть ли какой-то универсальный метод? Я главы по многочленам прочитал но что-то не помню чтобы в учебнике такой метод приводился или я что-то упустил.

[Brukvalub]

Судя по тому, что, например, во втором томе Лидла и Нидеррайтера есть спец. таблицы неприводимых многочленов, регулярного способа все их найти нет. Но в данном случае достаточно простого перебора. Например, все приводимые многочлены 4-й степени либо имеют корень, либо являются произведением двух неприводимых многочленов второй степени, и все это тривиально выписывается. Остается удалить из списка всех многочленов 4-й степени список приводимых, и останутся неприводимые. Аналогично и для 5-й степени.

[student1138]

Цитата:

Например, все приводимые многочлены 4-й степени либо имеют корень, либо являются произведением двух неприводимых многочленов второй степени

Мне эти утверждения совсем не очевидны. Например, почему многочлен 4й степени не может быть произведением двух приводимых многочленов 2й степени? А так же как их применить для решения задачи. Просто тупо перебором? Сначала проверять все возможные произведения многочленов степеней 1 и 3 а потом степеней 2?

[SomePupil]

student1138 в сообщении #1245348 писал(а):

Например, почему многочлен 4й степени не может быть произведением двух приводимых многочленов 2й степени?

Это когда корней нет.

student1138 в сообщении #1245348 писал(а):

Просто тупо перебором?

Ну да. К тому же, перебор можно сильно сократить, обрубив топором заведомо приводимые многочлены.

[student1138]

Цитата:

Это когда корней нет.

Имеется ввиду что если многочлен степени 2 разложим (на многочлены степеней 1) значит и у многочлена 4й степени есть множитель 1й степени т.е. корень? Такая логика?

[Brukvalub]

student1138 в сообщении #1245351 писал(а):

Имеется ввиду что если многочлен степени 2 разложим (на многочлены степеней 1) значит и у многочлена 4й степени есть множитель 1й степени т.е. корень? Такая логика?

Непохоже, что вы ранее многочленами интересовались...Вы бы сначала азы подучили, чтоле!

[SomePupil]

student1138 в сообщении #1245351 писал(а):

Такая логика?

Такая логика имеет право на жизнь.

Вы правильные вещи говорите, но своеобразно. Многие Вас будут ругать, надо вытерпеть.

[student1138]

Цитата:

Непохоже, что вы ранее многочленами интересовались...Вы бы сначала азы подучили, чтоле!

Почему это. Я просто пытался доказать ваше утверждение что если у многочлена 4й степени нет корней и он разложим на множители 2й степени то эти множители неприводимы.
Моя логика такая:
Если у многочлена 4й степени нет корней значит он не делится ни на какой многочлен вида $X-c$ (в случае $\mathbb{Z}_2$ это только $X-1, X-0$). Значит он разложим только на многочлены 2й степени. Но если какой-то из многочленов 2й степени разложим (т.е. делится на многочлен вида $X-c$) значит и исходный многочлен 4й степени на него делится. Противоречие.

[student1138]

В общем для степени 4 сделал так:
1) Сначала нашел единственый неприводимый многочлен 2й степени: $X^2 + X + 1$
2) Выписал все многочлены 4й степени и сразу выкинул те которые не заканчиваются на 1 (т.к. они делятся на X), осталось 8 многочленов.
3) Сразу проверил какой из них является квадратом многочлена $X^2 + X + 1$
4) Каждый из оставшихся семи по схеме Горнера проверил делится ли он на $X+1$
Те которые не делятся получается неприводимые:
$X^4 + X + 1$
$X^4 + X^3 + 1$
$X^4 + X^3 + X^2 + X + 1$

Не слишком громоздко получилось, может быть можно было по каким-то соображениям сократить перебор?

Кстати размышлял тут как оптимизировать процесс для степени 5 и понял вот что. Для проверки делимости на $X+1$ не обязательно делать полные вычисления по схеме Горнера. В данном случае достаточно посчитать количество ненулевых членов многочлена. Если оно четное - то многочлен делится на $X+1$ если нечетное то не делится. Это связано с тем что работаем в двоичной системе и остаток при рассчете по схеме Горнера в данном случае получается равен просто-напросто сумме всех коэффициентов многочлена.

[student1138]

Итак для 5й степени решил вот как. Для удобства стал записывать многочлены в виде последовательностей нулей и единиц (напр. $X^5+1 = 100001$ ).
1) Выписал 16 последовательностей у которых в начале и в конце 1
2) Из них вычеркнул те в которых число единиц четное (т.е. которые делятся на $X+1$) осталось 8 последовательностей:
100011
100101
101001
101111
110001
110111
111011
111101

3) Далее такое рассуждение: т.к. эти многочлены не делятся на многочлены 1й степени, то если они разложимы, они могут быть разложены только в произведение неразложимых многочленов 2й и 3й степени. Это следующие многочлены: $X^2+X+1$ и $X^3+X+1, X^3+X^2+1$. Считаем произведение и получаем два многочлена: 100011, 110001, их вычеркиваем
4) Таким образом получаем 6 неразложимых многочленов степени 5 над полем $\mathbb{Z}_2$:
100101
101001
101111
110111
111011
111101

Рассуждения верные?

[Cash]

в 2)

[student1138]

Cash в сообщении #1245414 писал(а):

в 2)

Да я уже успел исправить, техническая ошибка, упустил одну последовательность.

[Brukvalub]

student1138 в сообщении #1245402 писал(а):

4) Каждый из оставшихся семи по схеме Горнера проверил делится ли он на $X+1$

Проще было просто подставлять 1.

[VAL]

student1138,
Для самоконтроля полезно знать формулу для числа неприводимых над полем из $q$ элементов многочленов степени $n$ (ее вывод есть, например во 2-м параграфе 3-й главы 1-го тома Лидла и Нидеррайтера):

$$N_q(n)=\frac1n \sum_{d|n} \mu(d) q^{n/d} $$

Здесь $\mu(d)$ - функция Мебиуса.

В общем, случае для проверки многочленов на неприводимость есть алгоритм Берлекэмпа. Гуглите.
(Для Вашей задачи это, конечно, "стрельба из пушек по воробьям".)

[realeugene]

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

Проще было просто подставлять 1.

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