Найти минимальный многочлен элемента, используя неприводимый

[AndFed]

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

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

Спасибо.

от модератора AD:

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

[Sonic86]

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$.

[AndFed]

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

Спасибо.

[Sonic86]

Так, если что, книжка Лидл Нидеррайтер Конечные поля, попробуйте почитать, несложная.

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)$ найти методом неопределенных коэффициентов.
Если не получается - посмотрите у книжку, но лучше думать самому.

[RIP]

Есть простой алгоритм. Для начала надо найти характеристический полином $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$ (в данном случае он, очевидно, будет просто равен минимальному).

[Ales]

Может быть перейти к представлению:
$ 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)$).

[AndFed]

Нарешал я и сдал работу на проверку,преподаватель сказал не правильно и отправил на доработку. Если это не сложно, не могли бы Вы написать решение полностью, видимо не дано мне понять что куда здесь. Может хоть по готовому разберусь.

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

[Leox]

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).$

[Ales]

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

Может хоть по готовому разберусь.

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

[AndFed]

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$

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

[ИСН]

Что это за знаки: "3", "4"?

[AndFed]

ИСН в сообщении #328986 писал(а):

Что это за знаки: "3", "4"?

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

[Ales]

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$

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

[Leox]

я не уверен что етот способ гарантирует минимальность полученного многочлена