Поле. Нахождение корней полинома

[IPA47]

Здравствуйте
Помогите пожалуйста в решении следующей задачи:
В поле $\mathbb{F}_{2}[x]/(x^{4}+x+1)$ найти корни полинома $f(x)=x^4+x+1$ и выразить через них корни полинома $h(x)=x^4+x^3+x^2+x+1$.

Пытался сам решить, но пока решение дальше того факта, что $x^{4}=x+1$ не идет

[Joker_vD]

Для начала, давайте определимся с записью элементов поля $\mathbb F_2[x]/(x^4+x+1)$. Лично мне удобно писать $\overline{at^3+bt^2+ct+d}$. Вы не против? Если да, то попробуйте проверить, является ли корнем элемент $\overline t$.

[IPA47]

Сразу хочу задать вопрос на понимание по условию задачи, чтобы в дальнейшем не было неясностей: я правильно понимаю, что поле $\mathbb{F}_{2}[x]/(x^{4}+x+1)$ это множество полиномов вида $a+bx+cx^2+dx^3$, где $a, b, c, d \in \{0,1\}$, т.е. $\{a+bx+cx^2+dx^3 | a, b, c, d \in \{0,1\}\}$, ну или в Ваших обозначениях $\overline{at^3+bt^2+ct+d}$. И получается, что $x\in\{0, 1\}$, то есть, чтобы ответить на Ваш вопрос, я должен попытаться подставить $0$ и $1$ в уравнение $x^4+x+1=0$ и проверить справедливо ли равенство? Получается, что нет, $\overline t$ не является корнем данного полинома.

Идея видно такая: выписать все элементы(полиномы) исходного поля и, подставляя их все в полином $f(x)=x^4+x+1$ и проверяя потом, может ли $f$ быть нулем при $t=0 или t=1$, найти все корни для данного полинома в данном поле?

[Joker_vD]

IPA47 в сообщении #578168 писал(а):

Сразу хочу задать вопрос на понимание по условию задачи, чтобы в дальнейшем не было неясностей: я правильно понимаю, что поле $\mathbb{F}_{2}[x]/(x^{4}+x+1)$ это множество полиномов вида $a+bx+cx^2+dx^3$, где $a, b, c, d \in \{0,1\}$, т.е. $\{a+bx+cx^2+dx^3 | a, b, c, d \in \{0,1\}\}$, ну или в Ваших обозначениях $\overline{at^3+bt^2+ct+d}$.

Да, это так.

IPA47 в сообщении #578168 писал(а):

И получается, что $x\in\{0, 1\}$, то есть, чтобы ответить на Ваш вопрос, я должен попытаться подставить $0$ и $1$ в уравнение $x^4+x+1=0$ и проверить справедливо ли равенство?

Нет. Как это у вас получается? Вы должны подставлять в $x^4+x+1$ вместо $x$ элементы из расширения — т.е. $\overline{at^3+bt^2+ct+d}$. Я ж специально букву сменил, чтоб они не путались! Я тут с Unconnected несколько месяцев назад уже возился с похожей задачей.

Вот и подставьте в $x^4+x+1$ вместо икса $\overline{t}$. Должна произойти магия и чудеса, поразившие меня три года назад в самое сердце

[IPA47]

ну если я подставлю вместо икса $t$, то получу $t^4+t+1$ Следовательно, это не корень.
для x=t+1 получу тоже, то есть это тоже не корень
для $x=t^2$ получу 8 степень, и если я правильно понимаю, то степени выше 4 понижаются с помощью их выражения через степени более низкие, учитывая факт, что $t^4=t+1$ (это идет из равенства $x^4+x+1=0$). Тогда получим $t^8=(t^4)^2=(t+1)^2=t^2+1$, и в результате получим 0 и что $x=t^2$ корень. Так? И аналогично для других

[Joker_vD]

Вы $\overline t$ подставьте. Мы рассматриваем поле $\mathbb F_2[t]/(t^4+t+1)$, и многочлен над этим полем (не над $\mathbb F_2$!) $f(x)=\overline1x^4+\overline1x+\overline1$, который (допуская вольность в обозначениях), пишем как $x^4+x+1$.

[IPA47]

я получу $f(x)=\overline{t}^4+\overline t+1$. Только что-то видно я недопонимаю в Вашей записи. Что значит $\overline t$? Если для $\{a+bx+cx^2+dx^3 | a, b, c, d \in \{0,1\}\}$ договорились $\overline{at^3+bt^2+ct+d}$, то под $\overline t$ подразумеваются элементы $0t=0$ и $1t=t$ ?

Я вроде понимаю, что рассматриваем поле $\mathbb F_2[t]/(t^4+t+1)$, а не просто $\mathbb F_2$, иначе я бы не говорил, что поле состоит из полиномов степени ниже 4. У меня получилось, что всего в этом поле 16 элементов. Вот я и понял, что нужно каждый из 16 элементов подставлять вместо икса в уравнение и смотреть, получится ли 0 или нет. Получается - корень, нет - грусть, идем дальше. Разве не так?

[Joker_vD]

IPA47
Давайте начнем с самого самого начала. Возьмем поле $\mathbb F_2[t]/(t^4+t+1)$. Оно состоит из классов вычетов $\overline{at^3+bt^2+ct^1+d}=at^3+bt^2+ct^1+d+(t^4+t+1)$. Однако каждый такой класс записывается неоднозначно. Я могу написать $\overline0$, а могу — $\overline{t^4+t+1}$, и это будет один и тот же класс вычетов. Это пока понятно?

[IPA47]

да

[Joker_vD]

Хорошо. Я буду обозначать далее $\matbb F_2[t]/(t^4+t+1)$ как $K$. Итак, рассматриваем кольцо многочленов $K[x]$, а точнее, многочлен $f(x)=x^4+x+\overline{1}$. Его значением в точке $\overline{at^3+bt^2+ct+d}\in K$ называется сумма $(\overline{at^3+bt^2+ct+d})^4+\overline{at^3+bt^2+ct+d}+\overline{1}$. Если эта сумма равна $\overline{0}=\overline{t^4+t+1}$, это значение называется корнем многочлена.

[fenrixa]

Интересует та же задача, с той лишь разницей, что мне надо вырзаить через корни полинома $x^{4}+x^{3}+1$

Понятно, что само расширение состоит из 16 элементов, т.к. расширение 4й степени над $F_{2}$, это здорово, но.

Мысль поделить исходное на $x-t$ верна?

[fenrixa]

Корни получились $t$ и $t^{2}$, верно?

[tavrik]

IPA

какую книжку вы читаете по теме идеалов и колец?
и особенно, что стоит почитать о кольцах многочленов - приводимости над полями и тд...
thanks

[IPA47]

tavrik

Не очень понял вопроса. В чем подвох? Как видно из этой и предыдущей моей темы, я не особо разбираюсь в идеалах и кольцах...

-- 30.05.2012, 10:01 --

Получается: $\overline t^4+\overline t+\overline 1$ (даже не знаю, может стоит писать просто 1, все равно ведь понятно теперь, что по $\mod (t^4+t+1)$ надо считать), а если расписать $\overline t$ и взять от полинома $\mod (t^4+t+1)$, то получится, что $\overline t$ - корень. Верно?

[tavrik]

нет подвоха. я тоже не разбираюсь, учу сейчас.