Факторизация полиномов над кольцами вычетов высокой мощности

[Alek$]

Всем доброго времени суток.

Передо мною сейчас стоит такая практическая задача: необходимо строить многочлены над кольцами вычетов $\mathbb{Z}_{NM}$, где M и N — простые числа бит эдак от 256. Желаемая "на глазок" степень таких многочленов около 32. Впрочем, и степень, и мощность кольца можно увеличивать. Однако, к этим многочленам есть несколько требований разной степени критичности.

1. Их должно быть трудно факторизовать. Грубо говоря, их факторизация должна иметь примерно ту же трудоемкость, что и факторизация 1024-битных чисел.
2. Очень хочется, чтобы построенный полином был приводим над полем $\mathbb{Z}_N$ и неприводим — над кольцом $\mathbb{Z}_{NM}$.

Собственно, вопросов у меня несколько.

Во-первых, я был бы благодарен за ссылки на актуальные методы факторизации полиномов над кольцами вычетов, с учетом достаточно большой степени полиномов и мощности кольца. Насколько я в курсе, это сейчас делается исключительно путем разложения кольца $\mathbb{Z}_{NM}$ в $\mathbb{Z}_N \times \mathbb{Z}_M$, решением над каждым из этих полей и восстановлением окончательного решения по китайской теореме об остатках. Первая сложность на этом пути — это факторизация числа $MN$, что уже неплохо. Это приводит к двум подвопросам: насколько эффективные существуют алгоритмы решения полиномиальных уравнений над конечными полями вида $\mathbb{Z}_N$, и насколько сложно восстановить итоговое решение? Теория мне более-менее понятна, но практика вызывает вопросы...

Во-вторых, как строить полиномы, удовлетворяющие второму требованию? Тут у меня вообще внятных идей нет, может быть посоветуете направление поиска?

UPD. И да, хотелось бы, чтобы генерация таких полиномов была достаточно быстрой :)

UPD2. По второй проблеме единственное, что приходит в голову — строить полиномы, приводимые над $\mathbb{Z}_N$ и неприводимые над $\mathbb{Z}_M$, тогда они будут удовлетворять основному требованию. Но опять же, как это сделать, я не имею представления.

[Xaositect]

Первый вопрос, который у меня возник - зачем факторизовать полиномы, которые заведомо неприводимы?

По поводу построения и факторизации.
Неприводимые полиномы над полем вычетов $\mathbb{F}_p$ обычно генерируют так: берут случайный полином и проверяют его неприводимость. Вероятность получить приводимый полином достаточно хорошо падает с ростом степени. Неприводимость проверяется путем нахождения НОД с полиномами вида $x^{p^k} - x$, которые имеют в качестве корней вссе точки поля $\mathbb{F}_{p^k}$.
Приводимые полиномы генерировать еще легче - надо взять два случайных полинома и перемножить.
Для факторизации полиномов над $\mathbb{F}_p$ есть алгоритмы Берлекэмпа и Кантора-Цассенхауса. Они достаточно быстрые, факторизация полиномов 32 степени над 256-битным простым проблемой не является. Так что если у Вас $MN$ факторизуют, то считайте уже все.

[Alek$]

Xaositect, спасибо за ответ.

Если в кратце о том, для чего это нужно — это некоторый эксперимент из области криптографии.

Как построить просто полином приводимый или неприводимый в некотором поле я знаю. Но мне нужно построить такой полином, чтобы для двух заранее заданных колец $\mathbb{Z}_N$ и $\mathbb{Z}_{NM}$ он был приводим над первым и неприводим — над вторым. Один и тот же полином. У меня есть большие сомнения, что вероятностный алгоритм будет достаточно эффективен для таких условий.

За ссылки на алгоритмы спасибо, я изучу их. Быть может, удастся исхитриться, чтобы сделать их менее эффективными... Хотя, конечно, основная надежда на сложность факторизации NM.

[Xaositect]

Alek$ в сообщении #750685 писал(а):

Как построить просто полином приводимый или неприводимый в некотором поле я знаю. Но мне нужно построить такой полином, чтобы для двух заранее заданных колец $\mathbb{Z}_N$ и $\mathbb{Z}_{NM}$ он был приводим над первым и неприводим — над вторым. Один и тот же полином. У меня есть большие сомнения, что вероятностный алгоритм будет достаточно эффективен для таких условий.

"Один и тот же полином" - это когда один и тот же полином рассматривается по модулю $N$ и по модулю $NM$? В этом случае можно просто взять полином неприводимый по модулю $M$ и другой полином, приводимый по модулю $N$, и склеить их по китайской теореме.
А если хочется, чтобы это был совсем один и тот же полином, в смысле у него должны быть коэффициенты меньше $N$, то по-моему случайная генерация все равно будет работать Берем два полинома половинной степени, перемножаем их над $\mathbb{Z}_N$ и проверяем результат на неприводимость над $\mathbb{Z}_M$. По идее, почти всегда какие-то коэффициенты в произведении будут вылезать за $N$ и в этом случае я не вижу причин для полинома часто быть приводимым по другому простому модулю. Но вероятность я не не представляю как считать. Можно проверить экспериментально.

[Alek$]

Xaositect в сообщении #750746 писал(а):

"Один и тот же полином" - это когда один и тот же полином рассматривается по модулю

$$N$$

и по модулю

$$NM$$

?

Именно так.

Xaositect в сообщении #750746 писал(а):

В этом случае можно просто взять полином неприводимый по модулю

$$M$$

и другой полином, приводимый по модулю

$$N$$

, и склеить их по китайской теореме.

Я думал об этом, но пока я не очень понимаю один момент. Для применения китайской теоремы необходимо взять два взаимно простых многочлена $u_1(x)$ и $u_2(x)$, по модулю которых будут рассматриваться исходные многочлены. Вопрос состоит в том, исходя из каких соображений их выбирать, и могут ли они на что-то повлиять... Очевидно, что результат применения теоремы будет разный в зависимости от выбора.

[Xaositect]

Alek$ в сообщении #750888 писал(а):

Я думал об этом, но пока я не очень понимаю один момент. Для применения китайской теоремы необходимо взять два взаимно простых многочлена $u_1(x)$ и $u_2(x)$, по модулю которых будут рассматриваться исходные многочлены. Вопрос состоит в том, исходя из каких соображений их выбирать, и могут ли они на что-то повлиять... Очевидно, что результат применения теоремы будет разный в зависимости от выбора.

Под "склеить по китайской теореме" я имел в виду склеить каждый коэффициент.

[Alek$]

Понятно, спасибо. Теперь буду экспериментировать.