Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Мультипликативная группа поля GF(pm).
Пусть - неприводимый многочлен. Поле GF(pm) содержит pm элементов (22=4): {0};{1};{x};{1+x}. Из них pm-1 ненулевых элементов, составляют мультипликативную абелеву группу: {1};{x};{1+x}.
Итак, число элементов в этой группе – порядок группы равен pm-1.
Мультипликативная группа поля GF(pm) - циклическая группа.
{x} {x+1}
{x2}={x+1} {(x+1)2}={x}
{x3}={1} {(x+1)3}={(x+1)2(x+1)}=
порядок элемента {x} ={x(x+1)}={x2+x}={1}
равен 3= pm-1=22-1, порядок элемента {x+1}
т.е. {x}-примитивный элемент равен 3.
поля GF(23). {x+1} – примитивный элемент
поля GF(pm).
Если {αС}=1 и С≠ pm-1, то {α} – не примитивный элемент поля GF(pm).
Однако pm-1 делится на С (без остатка).
Отсюда, если βє GF(pm), то .
Следствие : .
Интересное соотношение:
α є GF(pm); b є GF(pm).
(a+b)p=ap+bp
Корни неприводимого многочлена из расширения поля.
Многочлен f(x)= неприводим.
Элементы 0 и 1 не являются его корнями.
Однако в поле по модулю f(x)= ещё два элемента:
{x}=α1; {x+1}=α2.
Является ли α1 корнем f(x)-?
α1- корень f(x) из расширения поля.
Является ли α2 корнем f(x)-?
Да! Отсюда у f(x) два корня из расширения поля.
Теорема 1. Если α – корень многочлена f(x) из расширения поля GF(pm), то αр – так же корень этого многочлена.
Дано: f(α)=a0+a1α+a2α2+…+amαm=0
Требуется доказать:
f(αp)= a0+a1αp+a2α2p+…+amαmp=0
Так как f(α)=0, то [f(α)]p=0,
Но
ч.т.д. [использовано: для поля GF(p):
]
Следствие: Если α – корень, то
Но .
1
Таким образом, у многочлена степени m ровно m корней.
Определение: Если α – примитивный элемент поля GF(pm) – корень многочлена f(x), то многочлен f(x) – примитивный многочлен.
Пример: α={x} - корень f(x)= .
Было показано, что {x} – примитивный элемент.
Отсюда f(x) – примитивный многочлен.
Теорема 2. Все элементы расширения поля GF(pm) являются корнями многочлена .
Док-во: В поле GF(pm) имеется pm элементов.
Многочлен pm имеет pm корней.
. Но любой ненулевой элемент α в степени равен 1. Отсюда любой элемент α или 0 – корень , ч.т.д.
Теорема 3.
Каждый неприводимый многочлен P(x) степени m над полем GF(p) является делителем многочлена
В поле GF(2):
Док-во: Из теоремы 2 следует:
где .
Многочлен P(x) степени m, неприводимый, имеет m корней в расширении поля GF(2m),
т.е.
отсюда делится на р(x), ч.т.д.
Задание многочлена его корнями.
Пусть дано поле GF(2m) (например, при m=2, по mod f(x)=x2+x+1).
Элементы этого поля: {0};{1};{x};{1+x} - 4 элемента (2m=22=4).
Требуется найти многочлен р(x), корнем которого является элемент α={x}.
Если α – корень p(x), то α2 также его корень, α4=α3α – его корень.
Но Отсюда у многочлена p(x) два корня: .
Откуда , т.е. уже ясно, что p(x) – второй степени.
.
=
Минимальная функция элемента α из GF(pm).
Нормированный многочлен минимальной степени такой, что α-его корень, называется минимальным многочленом или минимальной функцией α.
Теорема. Минимальная функция – неприводимый многочлен.
Обозначим m(x)-минимальный многочлен;
m(α)=0.
Доказательство: (от противного)
Предложим, что m(x)=m1(x)m2(x). Тогда m(α)=m1(α)m2(α)=0. Откуда следует, что есть многочлен степени меньшей m(x) такой, что α-его корень. Это противоречит условию.
Как найти минимальную функцию для α.
Найти минимальную функцию для α-это найти многочлен по его корню. (Уже было).
Двойственный многочлен.
Пусть P(x) – многочлен степени m.
Тогда
-
двойственный многочлен.
Пример:
Если P(x) примитивный многочлен, то также примитивный многочлен.