Файл: Контрольная работа Математические методы теории сетей связи.pdf
ВУЗ: Санкт-Петербургский государственный университет телекоммуникаций им. проф. М. А. Бонч-Бруевича
Категория: Методичка
Дисциплина: Сети связи
Добавлен: 25.10.2018
Просмотров: 4000
Скачиваний: 34
3) если многочлен f(x) неприводим, то f(x) и f
*
(x) принадлежат к одно-
му и тому же показателю.
Порядок корней неприводимого многочлена называется пока-
зателем, которому этот многочлен принадлежит. Если неприво-
димый многочлен принадлежит показателю е, то он является де-
лителем многочлена х
е
–1, но не является делителем никакого
многочлена х
n
–1 при n < e.
Показатель, которому принадлежит многочлен, находится
следующим образом. Пусть α – примитивный элемент GF(2
m
),
то-
гда прядок e элемента α
j
:
e = (2
m
–1)/HOД(2
m
–1, j),
с другой стороны, порядок e элемента α
j
указывает минимальную
степень многочлена х
e
–1, делителем которого является непри-
водимый многочлен, для которого
α
j
есть корень (НОД – наиболь-
ший общий делитель);
4) многочлен f
*
(x) примитивен тогда и только тогда, когда примитивен
f(x).
Возвращаясь к многочленам f(x) = x
4
+x+1 и f
*
(x) = x
4
+x
3
+1, отмечаем,
что все сказанное относительно двойственных многочленов справедливо
для этих многочленов:
- корни f(x) – α
1
, α
2
, α
4
, α
8
и корни f
*
(x) – α
7
, α
11
, α
13
, α
14
являются
элементами поля GF(2
4
), при этом α
1
α
14
= α
15
= 1; α
2
α
13
= α
15
= 1; α
4
α
11
=
α
15
= 1; α
8
α
7
= α
15
= 1;
- f(x) и f
*
(x) – неприводимые многочлены, при этом
f
7
(x) = x
4
f
1
(1/x) = x
4
(1+
4
3
4
1
1
)
1
x
x
x
x
;
- f
1
(x) и f
7
(x) принадлежат одному показателю 15, так как не являются
делителями никакого двучлена меньшей степени.
Проверить этот факт можно непосредственным делением х
5
+1, х
6
+1 и
т. д. на многочлены f
1
(x) и f
7
(x).
Найдем двучлен минимальной степени, делителем которого является
f
1
(x)f
7
(x) = f
17
(x) = (x
4
+x+1)(x
4
+
x
3
+1) = x
8
+x
7
+
x
5
+x
4
+x
3
+x+1.
Воспользуемся приемом [5], который эффективнее, чем последова-
тельное деление х
9
+1, х
10
+1 и т. д. на f
17
(x). Будем искать одночлен х
n
, оста-
ток от деления которого на f
17
(x) равен 1.
Остаток от деления х
8
на f
17
(x):
х
8
= x
7
+x
5
+x
4
+x
3
+x+1 (mod f
17
(x));
х
9
= x
8
+x
6
+x
5
+x
4
+x
2
+x =
x
7
+x
5
+x
4
+x
3
+x+1+x
6
+x
5
+x
4
+x
2
+x =
= x
7
+x
6
+x
3
+x
2
+1 (mod f
17
(x));
х
10
= x
8
+x
7
+x
4
+x
3
+x =
= x
7
+x
5
+x
4
+x
3
+x+1+x
7
+x
4
+x
3
+x =
= x
5
+1 (mod f
17
(x));
х
11
= x
6
+x (mod f
17
(x));
х
12
= x
7
+x
2
(mod f
17
(x));
х
1
3
= x
8
+x
3
= x
7
+x
5
+x
4
+x
3
+x+1+x
3
=
= x
7
+x
5
+x
4
+x+1 (mod f
17
(x));
х
14
= x
8
+x
6
+x
5
+x
2
+x =
= x
7
+x
5
+x
4
+x
3
+x+1+x
6
+x
5
+x
2
+x =
= x
7
+x
6
+x
4
+x
3
+x
2
+1 (mod f
17
(x));
х
1
5
= x
8
+x
7
+x
5
+x
4
+x
3
+x =
=x
7
+x
5
+x
4
+x
3
+x+1+x
7
+x
5
+x
4
+x
3
+x = 1(mod f
17
(x)).
Итак, х
15
+1 – двучлен минимальной степени, сомножителем которого
является (х
4
+х+1)(х
4
+х
3
+1).
2.2. Минимальные многочлены и их свойства
Выше было показано, что между корнями х
q
–х и элементами GF(q), где
q=p
m
существует однозначное соответствие, заключающееся в том, что ка-
ждый элемент β из GF(q) является корнем х
q
–х.
При этом коэффициенты многочлена х
q
–x и его неприводимых сомно-
жителей являются элементами поля GF(q). Элемент β, являясь корнем
х
q
–х,
является корнем одного из его сомножителей.
Минимальным многочленом элемента β из поля GF(p
m
)
назы-
вают нормированный многочлен минимальной степени m(x) с ко-
эффициентами из поля GF(p), такой, что m(β)=0.
Пример 2.2.1. Минимальные многочлены для элементов поля GF(2
4
):
Элемент
Минимальный многочлен
0
1
α
α
–
1
= α
1
4
α
3
α
5
х
х+1
х
4
+х+1
х
4
+х
3
+1
х
4
+х
3
+
х
2
+х+1
х
2
+х+1
Процесс нахождения минимальных многочленов будет обобщен в п. 2.4.
2.3. Свойства минимальных многочленов над полем GF(p)
1.
Минимальный многочлен неприводим.
Действительно, если m(x) = m
1
(x)m
2
(x), то m(β) =
m
1
(β) m
2
(β) = 0, то
либо m
1
(β) = 0, либо m
2
(β) = 0, что противоречит определению.
2.
Если некоторый многочлен f(x) с коэффициентами из GF(p)
такой, что f(β) = 0, то минимальный многочлен m(x) для β делит f(x).
Из свойства 2 имеем:
3.
Минимальный многочлен m(x) степени m является делите-
лем
m
p
x
x .
Из свойства 3 следует:
4.
Степени минимальных многочленов m(x) для элементов по-
ля GF(p
m
)
не превышают m.
С учетом сказанного, справедливо
5.
Если корень β является примитивным элементом GF(p
m
),
то m(x) для β имеет степень, равную m.
Как найти
( )
( )
i
m
x минимальный многочлен для β = α
i
из GF(p
m
)?
Если i лежит в циклотомическом классе
(
1)
,
m
s p
C
то
6.
(
1)
( )
( )
(
).
m
s p
i
j
j C
m
x
x
Из свойства 3 непосредственно вытекает:
7.
1
( )
1
( )
m
p
s
s
x
m
x
,
где s пробегает все множество представителей циклотомических классов по
модулю p
m
–1.
Полученный результат конкретизирует свойство 5.
Пример 2.3.1. В соответствии с данными примера 2.2.1 произведение
всех минимальных многочленов для элементов поля GF(2
4
) равно
х(х+1)(х
4
+х+1)(х
4
+х
3
+1)(х
4
+х
3
+х
2
+х+1)(х
2
+х+1)=х
16
+х, откуда
(х+1)(х
4
+х+1)(х
4
+х
3
+1)(х
4
+х
3
+х
2
+х+1)(х
2
+х+1)=х
15
+1.
2.4. Разложение х
n
–1 на неприводимые сомножители
Ранее циклотомические классы были определены по модулю p
m
–1. В
более общем случае можно определить циклотомический класс по модулю
n над GF(р) как множество
( )
s n
C
{s, sp, sp
2
, sp
1
s
m
},
где sp
s
m
s(mod n).
При этом множество всех чисел по модулю n разбивается на циклото-
мические классы
{0}, {1}, {l}, …, {n–1} =
(
1)
.
m
s p
s
C
Значение числа m
s
было определено выше. Cвязь между циклотомиче-
скими классами по модулю p
m
–1 и n определяется следующим образом:
число чисел m
1
в классе C
1(n)
равно степени расширения поля, для
которого многочлен степени m
1
,
является примитивным, т. е.
( )
,
s n
s
C
является составной частью
(
1)
,
m
s p
s
C
где
m = m
1
.
Например, для n = 9 и p = 2 имеем 3 циклотомических класса:
С
0(9)
= {0}, C
1(9)
= {1, 2, 3, 4, 8, 7, 5}, C
3(9)
= {3, 6}.
Это значит, что х
9
+1 над двоичным полем разлагается на 3 неприводи-
мых сомножителя: 1-й степени (х+1), 2-й степени (х
2
+х+1) и многочлен 6-й
степени. При этом порядок корней многочлена 2-й степени равен 3,так как
х
2
+х+1 принадлежит показателю 3, а порядок корней неприводимого мно-
гочлена 6-й степени равен 9 (принадлежит показателю 9).
В соответствии с сформулированными выше правилами х
9
+ 1 являет-
ся сомножителем
6
2
1
1
x
, так как класс С
1(9)
содержит 6 чисел, и корни
х
9
+1 могут быть выражены в виде степеней примитивного элемента поля
GF(2
6
).
Определим порядок пересчета корней
1
j
n
x
в элементы поля GF(p
m
),
т. е. найдем, какие корни
1
1
m
n p
x
являются корнями
1
j
n
x
, при усло-
вии, конечно, что n
j
меньше n и является его сомножителем .
Если порядок корней
1
n
x
есть е, а порядок корней его сомножите-
лей, принадлежащих показателю n
j
, т. е. входящих в разложение
1
j
n
x
,
где n
j
< n, равен
/
j
e
n n
, то, очевидно, образующий циклотомического
класса неприводимого многочлена f(x) по модулю n=p
m
–1, большего
n
j
и делящегося на него, в j = /
j
n n
раз больше образующего цик-
лотомического класса того же неприводимого многочлена.
Следовательно,
циклотомическому
классу
по
модулю
9
С
1(9)
= {1, 2, 4, 8, 7, 5} соответствует по модулю 63 циклотомический класс
С
7(63)
= {7,14,28,56, 49, 35}, так как =
63
9
= 7, а циклотомичекому классу
С
3(9)
= {3,6} соответствует циклотомический класс С
21(63)
= {21, 42}.
Как и ранее, подстрочный индекс в скобках в обозначении циклотоми-
ческого класса указывает модуль n
j
≤ n, по которому найдены последова-
тельности корней, отображаемых числами, входящими в циклотомический
класс, а число перед ним – образующий циклотомического класса.
Минимальное число n
j
в обозначении циклотомического класса данно-
го набора корней равно показателю, которому принадлежит многочлен с
данными корнями, т. е. порядку этих корней.
Заметим, что неприводимый многочлен, соответствующий некоторому
циклотомическому классу, является минимальным многочленом для кор-
ней, отображаемых этим циклотомическим классом.
Таким образом, разложение
1
n
x
на неприводимые сомножители
сводится к поиску минимальных многочленов для корней
1
n
x
.
Число корней, имеющих порядок е, определяется функцией Эйлера φ(е).
Если s − число, указывающее первый подстрочный индекс в обозначе-
нии циклотомического класса, то при модуле n=2
m
–1 порядок корней цик-
лотомического класса определяется следующим выражением:
2
1
HOÄ(2
1, )
m
m
e
s
.
Проиллюстрируем все отмеченное рассмотрением следующего примера.
Пример 2.4.1. Разложим х
63
+1 на неприводимые сомножители над
двоичным полем.
В соответствии с теоремой Ферма над полем GF(2)
х
63
+1=
63
0
(
)
i
i
x
, где α
i
GF(2
6
).
Таким образом, поиск неприводимых сомножителей х
63
+1 сводится к
распределению элементов поля GF(2
6
) α
i
по неприводимым сомножителям
х
63
+1 в соответствии с циклотомическими классами по модулю 63 и синте-
зу минимальных многочленов, соответствующих каждому циклотомиче-
скому классу.
Распределение элементов поля GF(2
6
) α
i
по неприводимым сомножи-
телям х
63
+1 в соответствии с циклотомическими классами по модулю 63
имеет вид: