2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Быстро сгенерироватьить неприводимый трёхчлен
Сообщение31.01.2013, 12:02 


07/01/11
55
Задача 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). Заранее спасибо!

 Профиль  
                  
 
 Re: Быстро сгенерироватьить неприводимый трёхчлен
Сообщение31.01.2013, 17:08 
Заслуженный участник


08/04/08
8562
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$ любой элемент - всегда кубичный вычет :roll: Сравнение $c^{\frac{p-1}{3}}\equiv 1\pmod p$ легко проверяется.
Вообще, достаточно взять кубический невычет $c$ и тогда $x^3-c$ неприводим по модулю $p$. Для $p\equiv -1 \pmod 3$ метод ничего не дает, к сожалению. Вам обязательно $a\neq 0$?
Также, если зафиксировать многочлен, то, скорее всего, простые числа разбиваются на конечное число классов вычетов по одному и тому же модулю, классов - 2 типа: по одному типу многочлен будет приводим, по другому - нет.
(есть еще кубичный закон взаимности, но, может, он тут не при чем)

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

 Профиль  
                  
 
 Re: Быстро сгенерироватьить неприводимый трёхчлен
Сообщение01.02.2013, 00:03 
Заслуженный участник
Аватара пользователя


18/12/07
762
Думаю, что 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$

 Профиль  
                  
 
 Re: Быстро сгенерироватьить неприводимый трёхчлен
Сообщение01.02.2013, 06:14 
Заслуженный участник


20/12/10
9062
Коровьев в сообщении #678616 писал(а):
Пусть $F$ – конечное поле, состоящее из $q$ элементов. Тогда для любого натурального $k\ge 1$ многочлен $x^{q^k } - x$ является произведением всех неприводимых над полем $F$ многочленов степени $k$.
Не совсем точно: в этом произведении будут все неприводимые многочлены, степень которых делит $k$. А что понимается под абсолютно неприводимым многочленом?

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

 Профиль  
                  
 
 Re: Быстро сгенерироватьить неприводимый трёхчлен
Сообщение01.02.2013, 10:45 
Заслуженный участник
Аватара пользователя


18/12/07
762
nnosipov в сообщении #678671 писал(а):
А что понимается под абсолютно неприводимым многочленом?


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

 Профиль  
                  
 
 Re: Быстро сгенерироватьить неприводимый трёхчлен
Сообщение23.02.2013, 09:22 


07/01/11
55
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$

 Профиль  
                  
 
 Re: Быстро сгенерироватьить неприводимый трёхчлен
Сообщение14.03.2013, 18:08 


15/06/12
56
По задаче 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$ решений), иначе приводим.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group