Помогите разобраться с расширенным полем Галуа

[alex_stp]

Здравствуйте! Задача следующая:
Найти элементы расширенного поля Галуа. Составить таблицы сложения и умножения элементов поля с использованием заданного полинома. Объяснить результат:
$GF(2^n)$
$f(x)=x^4+x^3+1$

не могу понять как составить множество $GF(2^4)$

заранее благодарю за ответы.

[Leox]

$GF(2^4)\cong \mathbb{Z}_2[x]/f(x)\mathbb{Z}_2[x]$
Другими словами - найдите все классы остатков от деления на $f(x)$ и покажите что они образуют поле.

[alex_stp]

т.е. найти остатки от деления:
$x^0/(x^4+x^3+1)$
$x^1/(x^4+x^3+1)$
.....
$x^{15}/(x^4+x^3+1)$
так?

[markiza]

$\{0, 1, x, x+1, x^2, x^2+x, x^2+1, x^2+x+1, x^3, x^3+x^2, x^3+x, x^3+1, x^3+x+1, x^3+x^2+x, x^3+x^2+1, x^3+x^2+x+1\}$
твое множество

[VAL]

alex_stp в сообщении #423867 писал(а):

т.е. найти остатки от деления:
x^0/x^4+x^3+1
x^1/x^4+x^3+1
.....
x^15/x^4+x^3+1
так?

Так, в принципе, тоже можно. Если Вам попрактиковаться в делении полиномов уголком над полем $\matbb Z_2$ охота :)
Но можно и сразу все возможные остатки выписать.
А попрактикуетесь, когда таблицу умножения (со сложением все тривиально) составлять будете, придется всякий раз заменять произведение остатком от деления на полином $x^4+x^3+1$.

[Joker_vD]

VAL
На самом деле нужно знать лишь остаток от деления $x^4$ на $x^4+x^3+1$, остальное быстрее достроить по дистрибутивности и уже выписанной части таблицы.

[VAL]

Joker_vD в сообщении #427138 писал(а):

VAL
На самом деле нужно знать лишь остаток от деления $x^4$ на $x^4+x^3+1$, остальное быстрее достроить по дистрибутивности и уже выписанной части таблицы.

Вы не поверите! Но множество из 16-и остатков будет то же!
Полином $x^4+x^3+1$ нужен лишь для выполнения умножения.
Насчет "остальное быстрее достроить по дистрибутивности", мягко говоря, очень сомневаюсь.
Как вы думаете, зачем в условии полином дан? Ведь поле из 16 элементов одно (с точностью до изоморфизма)

[Joker_vD]

VAL в сообщении #427160 писал(а):

Насчет "остальное быстрее достроить по дистрибутивности", мягко говоря, очень сомневаюсь.

Ну вот неделю назад я сдавал задание: построить поля $\mathbb F_3$, $\mathbb F_9$ как расширение $\mathbb F_3$, $\mathbb F_{27}$ как расширение $\mathbb F_3$ и $\mathbb F_{16}$ как расширение $\mathbb F_4$.

Потратил часа три на все про все. А дели я каждый раз в столбик... ладно, это кому как проще.

[VAL]

Joker_vD в сообщении #427166 писал(а):

VAL в сообщении #427160 писал(а):

Насчет "остальное быстрее достроить по дистрибутивности", мягко говоря, очень сомневаюсь.

Ну вот неделю назад я сдавал задание: построить поля $\mathbb F_3$, $\mathbb F_9$ как расширение $\mathbb F_3$, $\mathbb F_{27}$ как расширение $\mathbb F_3$ и $\mathbb F_{16}$ как расширение $\mathbb F_4$.

Потратил часа три на все про все. А дели я каждый раз в столбик... ладно, это кому как проще.

Во-первых, я бы не руками делил: воспользовался бы мат.пакетом, или программку за пять минут написал :)
Во-вторых, можно вообще не делить, учитывая тождества $x^4=x^3+1, \ x^5=x^3+x_1, \ x^6=x^3+x^2+x+1$.
В любом случае гарантирую, что за полчаса (это с запасом, если без компа) управлюсь.

[Joker_vD]

А! Так задание-то было — руками! Как преподаватель сказал, "Это вы во втором задании, где придется многочлены 20-ой степени раскладывать, будете пользоваться пакетами. А сейчас хоть раз в жизни поработайте с ними вживую".

Ну, мне проще сложить две колонки в таблице, чем перемножить два многочлена и сдергивать с него высокие степени по этим тождествам. Там больше времени на бумагомарание ушло.

[VAL]

Joker_vD в сообщении #427188 писал(а):

А! Так задание-то было — руками! Как преподаватель сказал, "Это вы во втором задании, где придется многочлены 20-ой степени раскладывать, будете пользоваться пакетами. А сейчас хоть раз в жизни поработайте с ними вживую".

Ну, если преподаватель сказал...
Кстати, а вы откуда это знаете? Или это гипотеза? Или Вы однокурсник ТС? Или тот самый преподаватель?
Насчет "хотя бы раз вживую" - согласен. И как преподаватель. И как автор книжки по конечным полям. Но я бы воспользовался мат.пакетом. Поскольку ручками (в одной из которых была ручка) уже считал. И даже больше одного раза

Цитата:

Ну, мне проще сложить две колонки в таблице, чем перемножить два многочлена

По модулю 2 это быстро.

Цитата:

и сдергивать с него высокие степени по этим тождествам.

Тоже легко.

Цитата:

Там больше времени на бумагомарание ушло.

Вам, конечно, самому решать, как вам решать :)
Но мой (точнее, общепринятый) метод идейнее. Ведь если поле большое, он дает возможность вести в нем вычисления (конечно, на компе) вовсе не храня таблицу умножения.

[Joker_vD]

VAL
Не, мы с топикстартером разные, я просто рассказываю случай из своей жизни Что там у ТС — не знаю.

VAL в сообщении #427201 писал(а):

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

Ну это да. С другой стороны, если сказали построить таблицу Кэли, ее как ни крути, а придется построить.