2014 dxdy logo

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

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




 
 Найти минимальный многочлен элемента, используя неприводимый
Сообщение26.05.2010, 00:21 
Задача:
Используя неприводимый над полем GF(2) многочлен $P(x)=1+x+x^3$, найти минимальный многочлен элемента $b=a^3$.

Почитал литературу, никак не могу понять даже как подходить к такой задаче. Я так понимаю "a" это какой-то "корень", при подстановке каторого многочлен будет равняться нулю. Помогите разобраться и решить задачу.

Спасибо.

 !  от модератора AD:
Формулы надо писать вот так, как я исправил.
В следующий раз в карантин отправлю :roll:

 
 
 
 Re: Дискретная математика - помогите решить задачу
Сообщение26.05.2010, 07:21 
AndFed писал(а):
Задача:
Используя неприводимый над полем GF(2) многочлен P(x)=1+x+x^3, найти минимальный многочлен элемента b=a^3.

Почитал литературу, никак не могу понять даже как подходить к такой задаче. Я так понимаю "a" это какой-то "корень", при подстановке каторого многочлен будет равняться нулю.


Видимо $a: 1+a+a^3=0$. Ну и надо найти для $b$ $Q(x): Q(b)=0$.

 
 
 
 Re: Дискретная математика - помогите решить задачу
Сообщение26.05.2010, 12:06 
Спасибо за ответ. Можно по подробней что к чему здесь? Слабоват я в этом. Вот есть неприводимый многочлен над полем из двух элементов (я так понимаю эти элементы 1 и 0). Т.е он не может быть разложен на более простые. Что значит с его помощью решить данную задачу? Как вообще снязан первый неприводимый многочлен и второй многочлен $\beta=\alpha^3$ ? Может есть какая теорема по этому поводу?

Спасибо.

 
 
 
 Re: Дискретная математика - помогите решить задачу
Сообщение26.05.2010, 12:24 
Так, если что, книжка Лидл Нидеррайтер Конечные поля, попробуйте почитать, несложная.
AndFed писал(а):
Вот есть неприводимый многочлен над полем из двух элементов (я так понимаю эти элементы 1 и 0). Т.е он не может быть разложен на более простые. Что значит с его помощью решить данную задачу?

Наверное надо так думать: $a$ такое, что $P(a)=a^3+a+1=0$ над $\mathbb{Z}_2$. То есть мы даем определение числу $a$ с помощью этого многочлена, поэтому зачем тут он - должно быть понятно.
AndFed писал(а):
Как вообще снязан первый неприводимый многочлен и второй многочлен $\beta = \alpha ^3$ ?

Не понял. Для начала не $\alpha$, а $a$ - именно то число, о котором писал выше, иначе $\alpha$ просто не определено. $b=a^3$ - это не многочлен, это тоже число. Для него надо найти какой-то многочлен $Q(x)$ такой, что $Q(b)=0$. Естественно Вам больше неоткуда взять $Q$ кроме как из условия $Q(b)=0$ и соотношения $a^3+a+1=0$. Вот и попробуйте. Это несложно. Тем более над $\mathbb{Z}_2$. Ну например, наиболее очевидный способ (но необязательно самый простой) - попробуйте $Q(x)$ найти методом неопределенных коэффициентов.
Если не получается - посмотрите у книжку, но лучше думать самому.

 
 
 
 Re: Дискретная математика - помогите решить задачу
Сообщение26.05.2010, 13:18 
Аватара пользователя
Есть простой алгоритм. Для начала надо найти характеристический полином $b$. Удобнее всего работать в базисе $1,a,a^2$. То есть считаете коэффициенты $a_{i,j}\in\mathbb F_2$ такие, что $b\cdot a^j=\sum_{i=0}^2a_{i,j}a^i$, а затем считаете характеристический полином матрицы $\|a_{i,j}\|_{i,j=0}^2$. Он равен (с точностью до $\pm$, смотря какие определения) некоторой степени минимального многочлена $b$ (в данном случае он, очевидно, будет просто равен минимальному).

 
 
 
 Re: Дискретная математика - помогите решить задачу
Сообщение26.05.2010, 15:28 
Может быть перейти к представлению:
$ a=\left( \begin{array}{lllll}
0 & 0 & 1 \\
1 & 0 & 1 \\
0 & 1 & 0 \\
\end{array} \right)$
Потом возвести матрицу в куб и найти характеристический многочлен.
Минимальный будет его делителем.

-- Ср май 26, 2010 15:32:59 --

$ b=a^3=a+1=\left( \begin{array}{lllll}
1 & 0 & 1 \\
1 & 1 & 1 \\
0 & 1 & 1 \\
\end{array} \right)$

-- Ср май 26, 2010 15:35:02 --

Матрица $a$ была подобрана так, чтобы ее характеристический многочлен совпал с заданным,
известно что характеристический многочлен аннулирует матрицу.
Это стандартный прием в алгебре, насколько я знаю.

-- Ср май 26, 2010 15:40:11 --

Алгебраические числа так изучают.

-- Ср май 26, 2010 15:43:30 --

Можно еще заметить, что $a=b+1$, значит $(b+1)^3+(b+1)+1=0$.
Раскрыть и проверить на приводимость (делится ли на $b,(b+1)$).

 
 
 
 Re: Дискретная математика - помогите решить задачу
Сообщение07.06.2010, 18:38 
Нарешал я и сдал работу на проверку,преподаватель сказал не правильно и отправил на доработку. Если это не сложно, не могли бы Вы написать решение полностью, видимо не дано мне понять что куда здесь. Может хоть по готовому разберусь. :oops:

Заранее спасибо.

 
 
 
 Re: Дискретная математика - помогите решить задачу
Сообщение08.06.2010, 00:03 
AndFed в сообщении #323942 писал(а):
Задача:
Используя неприводимый над полем GF(2) многочлен $P(x)=1+x+x^3$, найти минимальный многочлен элемента $b=a^3$.

Почитал литературу, никак не могу понять даже как подходить к такой задаче. Я так понимаю "a" это какой-то "корень", при подстановке каторого многочлен будет равняться нулю. Помогите разобраться и решить задачу.

Спасибо.


нуєно использовать явную формулу для минимального многочлена елемента. в вашем случае он равен в точности $(x-b) (x-b^2) (x-b^4).$
раскройте скобки и упростите, используя соотношение $a^3=a+1.$ После упрощение $a$ должно исчезнуть и получится многочлен над $GF(2).$

 
 
 
 Re: Дискретная математика - помогите решить задачу
Сообщение08.06.2010, 00:14 
AndFed в сообщении #328744 писал(а):
Может хоть по готовому разберусь.

Напишите, пожалуйста, сначала свое решение.

 
 
 
 Re: Дискретная математика - помогите решить задачу
Сообщение08.06.2010, 08:32 
Ales в сообщении #328931 писал(а):
AndFed в сообщении #328744 писал(а):
Может хоть по готовому разберусь.

Напишите, пожалуйста, сначала свое решение.


"Мое" решение было такое,
$P(x)=x^3+a+1$
$a^3+a+1=0$
$Q(x)$ такой, что $Q(b)=0$ и $a^3+a+1=0$
$a=b+1$ => $(b+1)^3+(b+1)+1=0$, раскрываем скобки и получаем
$Q(x)=x^3+3x^2+4x+3$

Может ошибка где-то в раскрытии или я что-то не понимаю, но конкретно что не правильно мне не сказали.

 
 
 
 Re: Дискретная математика - помогите решить задачу
Сообщение08.06.2010, 09:06 
Аватара пользователя
Что это за знаки: "3", "4"?

 
 
 
 Re: Дискретная математика - помогите решить задачу
Сообщение08.06.2010, 09:32 
ИСН в сообщении #328986 писал(а):
Что это за знаки: "3", "4"?

$Q(x)=x^3+x^2+x+1$ - так верно получается?

 
 
 
 Re: Дискретная математика - помогите решить задачу
Сообщение08.06.2010, 12:43 
AndFed в сообщении #328993 писал(а):
ИСН в сообщении #328986 писал(а):
Что это за знаки: "3", "4"?

$Q(x)=x^3+x^2+x+1$ - так верно получается?

Вы работаете с полем по модулю 2.
0 и 1, ложь и истина, четно и нечетно.
Четные числа заменяются на 0, нечетные на 1.

-- Вт июн 08, 2010 12:45:25 --

А так, до раскрытия скобок - правильно.

-- Вт июн 08, 2010 12:49:34 --

AndFed в сообщении #328977 писал(а):

$P(x)=x^3+a+1$
$a^3+a+1=0$
$Q(x)$ такой, что $Q(b)=0$ и $a^3+a+1=0$

Эти строчки лучше убрать.

 
 
 
 Re: Дискретная математика - помогите решить задачу
Сообщение08.06.2010, 16:14 
я не уверен что етот способ гарантирует минимальность полученного многочлена

 
 
 [ Сообщений: 14 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group