2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 Re: минимальный многочлен элемента поля GF(q)
Сообщение06.06.2010, 01:18 
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}})$

 
 
 
 Re: минимальный многочлен элемента поля GF(q)
Сообщение07.06.2010, 14:10 
откуда это такая формула сразу нарисовалась? пойду читать Лидла.

 
 
 
 Re: минимальный многочлен элемента поля GF(q)
Сообщение07.06.2010, 21:52 
endo в сообщении #328655 писал(а):
откуда это такая формула сразу нарисовалась? пойду читать Лидла.


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

 
 
 
 Re: минимальный многочлен элемента поля GF(q)
Сообщение08.06.2010, 06:54 
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$ + группа автоморфизмов циклическая?

 
 
 
 Re: минимальный многочлен элемента поля GF(q)
Сообщение08.06.2010, 16:12 
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$ + группа автоморфизмов циклическая?



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

 
 
 
 Re: минимальный многочлен элемента поля GF(q)
Сообщение10.06.2010, 15:37 
Итак. Во первых в условие задачи закралась ошибка. Степень примитивного многочлена по которому построено поле 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$.

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

 
 
 
 Re: минимальный многочлен элемента поля GF(q)
Сообщение10.06.2010, 18:56 
вопрос то в чем? формула для минимального многочлена у вас есть, теперь расскрывайте скобки, учитывая реализацию поля

 
 
 
 Re: минимальный многочлен элемента поля GF(q)
Сообщение11.06.2010, 09:37 
вопросов нет

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group