Здравствуйте!

Не могу справиться с задачей...

В поле $% F_2[x]/(x^4 + x + 1) $% найти корни полинома $% f(x) = x^4 + x + 1 $% и выразить через них корни полинома $% h(x) = x^4 + x^3 + x^2 + x + 1 $%.

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

задан 24 Апр '15 5:04

изменен 24 Апр '15 10:17

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

10|600 символов нужно символов осталось
3

Прежде всего, опишем строение самого поля, состоящего из $%2^4=16$% элементов. Многочлен $%x^4+x+1$% неприводим над $%\mathbb F_2$%, поэтому рассматриваемое факторкольцо действительно является полем. Обозначим через $%y$% образ многочлена $%x$% при естественном гомоморфизме. Тогда поле состоит из всех многочленов над $%\mathbb F_2$% вида $%a+by+cy^2+dy^3$%, где $%a,b,c,d\in\{0;1\}$%. Сложение производится обычным способом, а умножение задаётся так: сначала перемножаем два многочлена, а затем берём остаток от деления на $%y^4+y+1$%. Можно вместо взятия остатка использовать такие равенства: $%y^4=y+1$%; $%y^5=y^2+y$%; $%y^6=y^3+y^2$%.

Многочлен $%x^4+x+1$% имеет в поле из 16 элементов корень $%y$% по построению. Остальные корни получаются действием автоморфизмов поля. Группа автоморфизмов поля из $%p^n$% элементов является циклической порядка $%n$%, и её образующим является возведение в степень $%p$%. В нашем случае это возведение в квадрат. Применяя этот автоморфизм к элементу $%y$%, далее получим последовательно: $%y^2$%; $%y^4=y+1$%; $%(y+1)^2=y^2+1$%. Это даёт ещё три корня. Заметим, что при следующем возведении в квадрат мы бы снова пришли к $%y$%, как и должно быть: $%(y^2+1)^2=y^4+1=y+1+1=y$%.

Таким образом, $%x^4+x+1=(x-y)(x-y^2)(x-(y+1))(x-(y^2+1))$% -- разложение на линейные множители.

Во втором задании мне не совсем понятно, что имелось в виду под словом "выразить". Это можно сделать очень многими способами. Прежде всего, найдём сами корни многочлена $%h(x)$%. Заметим, что $%h(x)=\frac{x^5-1}{x-1}$% при $%x\ne1$%. Следовательно, в качестве корня подойдёт элемент, отличный от 1, равный 1 в пятой степени. Поскольку поле у нас состоит из 16 элементов, его мультипликативная группа имеет 15 элементов, и потому любой элемент в 15-й степени равен 1. Поэтому в качестве одного из корней подходит $%y^3$%. Далее действуем автоморфизмом, получая $%y^6=y^3+y^2=y^2(y+1)$%. После следующего возведения в квадрат получится $%y^4(y+1)^2=(y+1)(y^2+1)=y^3+y^2+y+1$%. Возводя ещё раз в квадрат, получим $%(y+1)^2(y^2+1)^2=(y^2+1)y=y^3+y$%.

Таким образом, мы нашли все 4 корня многочлена $%h(x)$%. Все они выражены через $%y$%, что уже можно считать выражением этих корней через корни $%f(x)$%. Но можно также заметить, что если $%y_i$% ($%i=1,2,3,4$%) -- корни $%f(x)$%, то корнями $%h(x)$% будут их кубы: $%y_i^3$%. Помимо этого, можно заметить, что если корни многочлена $%f(x)$% перечислены в том порядке, как они выписаны, то корнями $%h(x)$% окажутся элементы $%y_1y_2$%, $%y_2y_3$%, $%y_3y_4$%, $%y_4y_1$%.

ссылка

отвечен 24 Апр '15 11:47

изменен 28 Апр '15 2:54

@falcao, Извините, пожалуйста, а что значит фраза "Многочлен $% x^4+x+1 $% имеет в поле из 16 элементов корень $% y $% по построению."

(28 Апр '15 0:27) Ice_Fox
1

@Ice_Fox: поле построено как факторкольцо по идеалу $%I$%. Его элементами являются смежные классы по идеалу вида $%p(x)+I$%, где $%p(x)$% -- произвольный многочлен. Рассмотрим элемент $%x+I$%, обозначая его через $%y$%. По правилам сложения и умножения смежных классов, $%y^4+y+1=(x^4+x+1)+I=I$% -- последнее равенство очевидно. Остаётся заметить, что $%I$% есть нулевой элемент факторкольца. Тогда более привычно это равенство будет выглядеть в форме $%y^4+y+1=0$%. Это и значит, что $%y$% является корнем указанного многочлена. Это рассуждение почти тавтологично по сути.

(28 Апр '15 0:46) falcao

@falcao, спасибо большое, это осознала... Если Вас не затруднит, не могли бы Вы еще пояснить момент: "Поскольку поле у нас состоит из 16 элементов, его мультипликативная группа имеет 15 элементов, и потому любой элемент в 15-й степени равен 1"... Это следует из того, что группа циклическая?

(28 Апр '15 1:36) Ice_Fox
1

@Ice_Fox: группу образуют все элементы поля кроме нуля. Их 15. По следствию из теоремы Лагранжа о подгруппах, если в группе $%n$% элементов, то $%g^n=1$% для любого элемента $%g\in G$%. Это верно для любой группы -- в том числе нециклической. Факт цикличности мультипликативной группы конечного поля -- утверждение куда более нетривиальное. В данном случае оно не используется.

Кстати, верен такой факт, что любая группа порядка 15 циклическая. Но это также не используется.

(28 Апр '15 1:49) falcao

@falcao, осознала, спасибо большое. И, наверное, последний вопрос... В строчке $% (y+1)^2(y^2+1)^2=(y^2+1)y=y^3+y^2 $% разве последнее слагаемое не должно быть просто $% y $%... Почему квадрат?..

(28 Апр '15 2:45) Ice_Fox

@Ice_Fox: конечно, $%y^3+y$% должно быть. Это описка. Я сейчас её исправлю. Спасибо, что заметили.

(28 Апр '15 2:53) falcao

@falcao, Вам спасибо огромное за помощь) Я все-таки поняла задачку..)

(28 Апр '15 2:56) Ice_Fox
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,259
×118
×55

задан
24 Апр '15 5:04

показан
1297 раз

обновлен
28 Апр '15 2:56

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru