Разложить многочлен в кольце.

[Sonic86]

PWT в сообщении #1131242 писал(а):

Тогда ответ на этот вопрос "да"?

Да.

PWT в сообщении #1131242 писал(а):

б) Если оказывается равенство верным для некоторого $k\in \mathbb{Z}$, то далее делим уголком на $(x-a)$ и получаем

$P(x)=(x-a)Q(x)+5k\equiv (x-a)Q(x) (\bmod 5)$

в) У многочлена $Q(x)$ степень на единицу меньше, далее проверяем $Q(x)$ аналогично и постепенно раскладываем до тех пор, пока не будет находится некоторый $k\in \mathbb{Z}$, для которого выполнено равенство из пункта $(a)$. Но как дальше тогда? Или на этот вопрос уже гораздо сложнее ответить? Правильно ли я представляю алгоритм?

Так это только начало. Так Вы сможете найти только делители степени 1, а делители степени выше найти не сможете. Например, $(x^2+2)^2=x^4+4x^2+4$ Вы так не разложите.
Под перебором в общем случае понимался перебор всевозможных делителей, коих довольно много.
Дальше, когда перебор надоест или станет неэффективным - Берлекэмп.

[PWT]

Хорошо, спасибо. А когда заведомо разложить не получится в этом же кольце? Есть ли какие-то признаки этого?

[Sonic86]

Простых признаков неприводимости многочлена над полем вычетов я не знаю.

[VAL]

Sonic86 в сообщении #1131294 писал(а):

Простых признаков неприводимости многочлена над полем вычетов я не знаю.

А из не очень простых опять Берлекэмп.
Многочлен $n$-й степени неприводим над данным конечным полем тогда и только тогда, когда ранг матрицы Берлекэмпа равен $n-1$.

В принципе, такая проверка не слишком сложна по сравнению с полным алгоритмом Берлекэмпа.

[Sonic86]

А что если пообобщать малую теорему Ферма и признак Люка-Лемера (который поиск образующего у циклической группы)? Наверняка же пробовали.

Т.е. пусть $f(x)$ степени $n$ - неприводим над $\mathbb{Z}_p$. Тогда $F=\mathbb{Z}_p[x]/(f(x))=GF(p^n)$ - конечное поле порядка $p^n$ с цикличной мультипликативной группой. Тогда для любого $h\in F$ $h^{p^n-1}=1$ - это должно быть необходимое условие, но не достаточное (т.е. д.б. аналоги чисел Кармайкла - числа $p^n$). Вот его можно проверять.
А поиск образующего мультипликативной группы должен давать такой критерий:
Если $g\in F$ - такое, что $g^{p^n-1}=1$, но для любого $d:d|p^n-1$ $g^{\frac{p^n-1}{d}}\neq 1$, то $f$ - неприводим над $\mathbb{Z}_p$. И обратное тоже верно.

Это верно?
И тоже должно быть эффективно, особенно поиск образующей: $p^n-1$ раскладывается на множители очень хорошо, особенно если с $n$ повезет.