Быстро сгенерироватьить неприводимый трёхчлен

[Bars]

Задача 1. Дано простое число $p$. Найти $a$ и $b$ такие, чтобы многочлен $h(x) = x^3 + ax + b$ был неприводим над полем $\mathbb Z_p$.

Есть идеи, как для данных $a$ и $b$ проверить приводимость $h(x)$. И понятно, что в среднем случае перебор будет работать быстро, так как число неприводимых многочленов $h(x)$ должно быть пропорционально $p$. Но в худшем случае придется перебрать полполя. Другое дело, если бы был способ сразу получить нужные $a$ и $b$.

Задача 2. А что, если $p$ составное

Задача 3. А что, если $p$ произволоное

Подскажите, пожалуйста, где я могу поискать ответь (хотябы на задачу 1). Заранее спасибо!

[Sonic86]

Bars в сообщении #678219 писал(а):

Задача 3. А что, если $p$ произволоное

Задачи 1 и задачи 2 дают Вам ответ для почти любого натурального числа. В задаче 3 Вы спрашиваете не про натуральное $p$? Это какое например?

Bars в сообщении #678219 писал(а):

Задача 2. А что, если $p$ составное

Если $p$ составное, то $\mathbb{Z}_p$ - это не поле. Вам этот вариант точно нужен?

Bars в сообщении #678219 писал(а):

Задача 1. Дано простое число $p$. Найти $a$ и $b$ такие, чтобы многочлен $h(x) = x^3 + ax + b$ был неприводим над полем $\mathbb Z_p$.

Можно воспользоваться формулой Кардано для корней кубического уравнения. Например, если корень имеет вид $\sqrt[3]{A}+\sqrt[3]{B}$, то можно просто проверить являются ли $A,B$ кубичными вычетами по модулю $p$ нет. Элемент $c$ - кубичный вычет по модулю $p:p\equiv 1\pmod 3$ $\Leftrightarrow c^{\frac{p-1}{3}}\equiv 1\pmod p$, а при $p\equiv -1\pmod 3$ любой элемент - всегда кубичный вычет Сравнение $c^{\frac{p-1}{3}}\equiv 1\pmod p$ легко проверяется.
Вообще, достаточно взять кубический невычет $c$ и тогда $x^3-c$ неприводим по модулю $p$. Для $p\equiv -1 \pmod 3$ метод ничего не дает, к сожалению. Вам обязательно $a\neq 0$?
Также, если зафиксировать многочлен, то, скорее всего, простые числа разбиваются на конечное число классов вычетов по одному и тому же модулю, классов - 2 типа: по одному типу многочлен будет приводим, по другому - нет.
(есть еще кубичный закон взаимности, но, может, он тут не при чем)

Вот такая тема была когда-то, там просто пример разобран.

[Коровьев]

Думаю, что Bars интересует вопрос об алгоритме построения неприводимых кубических многочленов для быстрой генерации ключей шифрования. Тут изучать спец.литературу надо, а её сейчас ой как много.
"Сразу получить нужные $a$ и $b$" наверно не удастся ибо, насколько я помню, есть теорема о том что, если дискриминант кубического многочлена есть квадратичный вычет по модулю $P$, то либо многочлен абсолютно неприводим в поле $\mathbb Z_p$, либо целиком раскладывается в нём на линейные множители. А вот это "либо" надо проверять руками.

Есть алгоритмы основанные на следующей теореме .
Пусть $F$ – конечное поле, состоящее из $q$ элементов. Тогда для любого натурального $k\ge 1$ многочлен $x^{q^k } - x$ является произведением всех неприводимых над полем $F$ многочленов степени $k$.

Вот ещё из теории алгебраических чисел. Для любого простого $P \equiv 1(\bmod 3)$
можно построить бесконечно много кубических многочленов, неприводимых в поле рациональных чисел, и которые абсолютно неприводимы в поле $\mathbb Z_p$ для определённого класса простых чисел.
К примеру. Абсолютно неприводимый многочлен $f(x) = x^3 + x^2 - 2x - 1$ абсолютно неприводим в поле $\mathbb Z_p$ для простых чисел вида $P = 7k \pm 2, \pm 3$ и разложим в нём на линейные множители для простых чисел вида $P = 7k \pm 1$

[nnosipov]

Коровьев в сообщении #678616 писал(а):

Пусть $F$ – конечное поле, состоящее из $q$ элементов. Тогда для любого натурального $k\ge 1$ многочлен $x^{q^k } - x$ является произведением всех неприводимых над полем $F$ многочленов степени $k$.

Не совсем точно: в этом произведении будут все неприводимые многочлены, степень которых делит $k$. А что понимается под абсолютно неприводимым многочленом?

Для задачи 1 достаточно находить $\gcd{(x^{p-1}-1,x^3+ax+b)}$.

[Коровьев]

nnosipov в сообщении #678671 писал(а):

А что понимается под абсолютно неприводимым многочленом?

Это мой личный ляп, поскольку переменная там только одна.

[Bars]

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

Bars в сообщении #678219 писал(а):

Задача 3. А что, если $p$ произволоное

Задачи 1 и задачи 2 дают Вам ответ для почти любого натурального числа. В задаче 3 Вы спрашиваете не про натуральное $p$? Это какое например?

Я имел в виду, что априори неизвестно, является ли $p \in \mathbb N$ простым

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

Bars в сообщении #678219 писал(а):

Задача 2. А что, если $p$ составное

Если $p$ составное, то $\mathbb{Z}_p$ - это не поле. Вам этот вариант точно нужен?

Да, здесь нужен $h(x)$, неприводимый над кольцом $\mathbb Z_p$

[VladimirKr]

По задаче 1 могу высказаться:
Очень давно я решал подобную задачу, правда там был нужен трехчлен степени 127 над $GF(2)$.
Унитарный многочлен $f(x)$ над конечным полем порядка $q$, не имеющий кратных корней неприводим тогда и только тогда, когда многочлен $x^q-x$ имеет ровно $q$ корней в кольце $GF(q)/f(x)$ (Критерий Батлера).
Почти очевидно, но достаточность доказывается не в одну строчку.
1. Проверяем на взаимную простоту с производной, не взаимнопрост - приводим
2. Производим тест Батлера.
Ну, грубо говоря, начинаем решать уравнение $x^q-x$ в кольце $GF(q)/f(x)$. Если аккуратно расписать используя равенство для полей порядка $q$ равенство $(a+b)^q=a^q+b^q$, то получится однородная система линейных уравнений над $GF(q)$ размерности $n$x$n$ $, где n=deg f(x)$. Если ранг системы равен $n-1$, то $f(x)$ неприводим (система иммеет $q$ решений), иначе приводим.