Разложить полином на неприводимые множители

[Mary84]

Задача: разложить на неприводимые множители полином $x^5+x^4+4x^3+3x^2+3x+5 $ в кольце $ \mathbb{F}_7[x]$.

Делителями полинома могут быть полиномы степени не выше четвёртой, с коэффициентами $0, 1, 2...6$. Эта задача решается перебором? Т.е. надо построить все возможные полиномы и поочерёдно делить на них исходный? Больше идей нет. Подскажите, пожалуйста, как решать.

[Deggial]

Многочлен легко раскладывается на 2 множителя.
Подсказка: $5\equiv 3\cdot 4\pmod 7$

Mary84 в сообщении #871397 писал(а):

Делителями полинома могут быть полиномы степени не выше четвёртой

А если рассмотреть делитель с минимальной степенью?

[nnosipov]

Mary84 в сообщении #871397 писал(а):

Эта задача решается перебором?

Методов факторизации многочленов над конечным полем много. Наиболее известный --- алгоритм Берлекэмпа. Этот алгоритм детерминированный. А есть ещё вероятностные, например метод Кантора-Цассенхауза. Наконец, можно просто угадать ответ, на что Вам уже намекнули.

[Mary84]

Рассмотрим делители с минимальной степенью. Попробовала разделить на $(x-1),...,(x-6)$, но везде остаток получился.

-- 03.06.2014, 19:37 --

(Оффтоп)

Точно не по алгоритму Берлекэмпа или Кантора-Цассенхауза, мы таких не проходили на лекциях и упражнениях. Но интересно было узнать, что такие есть.

[nnosipov]

Значит, предполагается наивный подход --- метод проб и угадываний. То, что линейных делителей нет, Вы уже проверили. Осталось найти разложение в произведение квадратного и кубического многочленов.

[Mary84]

Спасибо большое, разобралась)