минимальный многочлен элемента поля GF(q)

[endo]

Имеем конечное поле GF(16), q=2, m=4. Поле построено по примитивному многочлену $p(x)=x^3+x+1$. Как найти минимальный многочлен для каждого элемента поля GF(16), построенного как расширение поля GF(2)?

[Sonic86]

Так, Вам нужна книжка Лидл Нидеррайтер Конечные поля. Большая, но несложная.
А насчет вашей задачи точно не вспомню сейчас.
1. Вы можете найти минимальный многочлен для какого-то одного элемента, а затем, используя автоморфизмы поля, найти минимальные многочлены для остальных элементов.
2. Любой ненулевой элемент удовлетворяет уравнению $x^{q^m}-x=0$ (это потому что поле, и у него мультипликативная группа конечная и циклична). Можно разложить на множители над полем и отсюда попытаться, что-то найти, но честно говоря не уверен - думайте пока.

[Leox]

endo в сообщении #327601 писал(а):

Имеем конечное поле GF(16), q=2, m=4. Поле построено по примитивному многочлену $p(x)=x^3+x+1$. Как найти минимальный многочлен для каждого элемента поля GF(16), построенного как расширение поля GF(2)?

минимальный многочлен елемента $\alpha$ равен $(x-\alpha) (x-\alpha^2) \cdots (x-\alpha^{2^{m-1}})$

[endo]

откуда это такая формула сразу нарисовалась? пойду читать Лидла.

[Leox]

endo в сообщении #328655 писал(а):

откуда это такая формула сразу нарисовалась? пойду читать Лидла.

в Лидла, том.2, стр. 605
или любую книгу по алгебраической теории кодирования

[Sonic86]

Leox писал(а):

минимальный многочлен елемента $\alpha$ равен $(x-\alpha)(x-\alpha ^2)...(x-\alpha ^{2^{m-1}})$

Leox, я же правильно понимаю, что это даже общая формула: минимальный многочлен $h(x)$ в поле $P$ элемента $\alpha$ равен $(x-\alpha)(x-f(\alpha) )...(x-f^{2^{m-1}}(\alpha))$, где $f$ - автоморфизм поля $P[\alpha]$ + еще то, что автоморфизм $GF(q^m)$ - это $f: x \to x^q$ + группа автоморфизмов циклическая?

[Leox]

Sonic86 в сообщении #328966 писал(а):

Leox писал(а):

минимальный многочлен елемента $\alpha$ равен $(x-\alpha)(x-\alpha ^2)...(x-\alpha ^{2^{m-1}})$

Leox, я же правильно понимаю, что это даже общая формула: минимальный многочлен $h(x)$ в поле $P$ элемента $\alpha$ равен $(x-\alpha)(x-f(\alpha) )...(x-f^{2^{m-1}}(\alpha))$, где $f$ - автоморфизм поля $P[\alpha]$ + еще то, что автоморфизм $GF(q^m)$ - это $f: x \to x^q$ + группа автоморфизмов циклическая?

Выглядит очень правдоподобно

[endo]

Итак. Во первых в условие задачи закралась ошибка. Степень примитивного многочлена по которому построено поле GF(16) должна быть равна 4: $x^4+x+1$. Для начала построим поле. Для этого найдем все элементы поля и зададим таблицей правило сложения и умножения любых пар элементов поля.
Примитивный многочлен в двоичном виде: 10011. Воспользуемся цикличностью поля. Выберем элемент $\alpha^0=1$ и будем сдвигать его последовательно в сторону старших разрядов. При переполнении разрядной сетки сложим число с примитивным многочленом и получим новый элемент поля. Построение поля закончится как только элемент $\alpha^0=1$ повторится.
1|0011
0000 - нулевой элемент по сложению

0001 $\alpha^0$
0010 $\alpha^1$
0100 $\alpha^2$
1000 $\alpha^3$
0011 $\alpha^4$
0110 $\alpha^5$
1100 $\alpha^6$
1011 $\alpha^7$
0101 $\alpha^8$
1010 $\alpha^9$
0111 $\alpha^1^0$
1110 $\alpha^1^1$
1111 $\alpha^1^2$
1101 $\alpha^1^3$
1001 $\alpha^1^4$

0001 $\alpha^1^5$=$\alpha^0$

Итого получили $q^m-1$ элементов поля от $\alpha^0$ до $\alpha^1^4$.

Продолжение следует...

[Leox]

вопрос то в чем? формула для минимального многочлена у вас есть, теперь расскрывайте скобки, учитывая реализацию поля

[endo]

вопросов нет