Файл: Контрольная работа Математические методы теории сетей связи.pdf

С

0(63)

= {0}  

С

1(63)

= {1, 2, 4, 8, 16,32} 

С

3(63)

= {3, 6, 12, 24, 48, 33} 

С

5(63)

= {5, 10, 20, 40, 17, 34} 

С

7(63)

= {7, 14, 28, 56, 49, 35} 

С

9(63)

= {9, 18, 36} 

С

11(63)

= {11, 22, 44, 25, 50, 37} 

С

13(63)

= {13,26, 52, 41, 19, 38} 

С

15(63)

= {15, 30, 60, 57, 51, 39} 

С

21(63)

= {21,42} 

С

23(63)

= {23,46, 29, 58, 53, 43} 

С

27(63)

= {27, 54, 45} 

С

31(63)

= {31,62, 61 ,59, 55,47} 

В  табл.  2.4.1  приведены  многочлены,  соответствующие  найденным 

циклотомическим классам, и порядок их корней. 

Таблица 2.4.1 

Циклото-

мический 

класс 

Состав  

циклотомического  

класса 

Минимальный 

многочлен 

Порядок корней 

многочлена 

63

HOÄ( , 63)

e

s



С

0(63)

{0 = 63} 

х+1 

1 

С

1(63)

{1, 2, 4, 8, 16, 32} 

х

6

+х+1 

63 

С

3(63)

{3, 6, 12, 24, 48, 33} 

х

6

+х

4

+

х

2

+х+1 

21 

С

5(63)

{5, 10, 20, 40, 17, 34} 

х

6

+х

5

+х

2

+х+1 

63 

С

7(63)

{7, 14, 28, 56 49, 35} 

х

6

+х

3

+1 

9 

С

9(63)

{9, 18, 36} 

х

3

+х

2

+1 

7 

С

11(63)

{11, 22, 44, 25, 50, 37} 

х

6

+х

5

+х

3

+х

2

+1 

63 

С

13(63)

{13, 26, 52, 41, 19, 38} 

х

6

+х

4

+х

3

+х+1 

63 

С

15(63)

{15, 30, 60, 57, 51, 39} 

х

6

+х

5

+х

4

+х

2

+1 

21 

С

21(63)

{21,42} 

х

2

+х+1 

3 

С

23(63)

{23, 46, 29, 58, 53, 43} 

х

6

+х

5

+х

4

+х+1 

63 

С

27(63)

{27, 54, 45} 

х

3

+х+1 

7 

С

3

1(63)

{31, 62, 61, 59, 55, 47} 

х

6

+

х

5

+1 

63 

Многочлены получены из таблиц, приведенных в [1] и помещенных в 

приложении. Правила пользования таблицами приводятся ниже. 

Анализ приведенных в табл. 2.4.1 многочленов показывает, что в раз-

ложение 

6

63

2

1

1

1

x

x



 



  входят  многочлены  1,  2,  3  и  6-й  степеней.  Эти 

числа  представляют  все  делители  числа  6.  Порядок  корней  многочленов 

указывает, какому показателю принадлежат многочлены. 

Если  воспользоваться  функцией  Эйлера,  можно  определить  число 

элементов  поля  GF(2

6

),  принадлежащих  указанным  в  таблице  порядкам  

1, 3, 7, 9, 21, 63: 

φ(1) = 1 − это один корень х+1,  
φ(3) = 2 − это два корня х

2

+х

3

+1,  

φ(7) = 6 − это корни двойственных многочленов х

3

+х

2

+1 и х

3

+х+1, 

φ(9) = 6 − это корни самодвойственного многочлена х

6

+х

3

+1,  

φ(21)  =  12  –  это  корни  двойственных  многочленов:  х

6

+х

4

+х

2

+х+1  и 

х

6

+х

5

+х

4

+х

2

+1, 

φ(63) = 32 − это корни 6 примитивных попарно двойственных много-

членов  х

6

+х+1  и  х

6

+х

5

+1,  х

6

+х

5

+х

2

+х+1  и  х

6

+х

5

+х

4

+х+1,  х

6

+х

5

+х

3

+х

2

+1  и 

х

6

+х

4

+х

3

+х+1. 

На этом процесс разложения х

63

+1 на неприводимые сомножители за-

вершен. 

Пример  2.4.2.  Построить  циклотомические  классы  по  модулю  степе-

ней двучленов, делящих х

63

+1. 

х+1,  
j = 63 

С

0(1)

= {0 = 1} 

С

0(63)

= {0 = 63} 

х

3

+1,  

j = 21 

С

0(3)

= {0 = 3}  

С

1(3)

= {1, 2} 

С

0(63)

= {0 = 63} 

С

21(63) 

= {21, 42} 

х

7

+1,  

j = 9 

С

0(7)

= {0 =7} 

С

1(7)

= {1, 2, 4} 

С

3(7)

= {3, 6, 5} 

С

0(63)

= {0 = 63} 

С

9(63)

= {9, 18, 36} 

С

27(63)

= {27, 54, 45} 

х

9

+1,  

j = 7       

С

0(9)

= {0 = 9}  

С

1(9)

= {1, 2, 4, 8, 7, 5} 

С

3(9)

= {3, 6} 

С

0(63)

= {0 = 63} 

С

7(63)

= {7, 14, 28, 56, 49, 35} 

С

21(63)

= {21, 42} 

х

21

+1, 

j = 3      

С

0(21)

= {0 = 21}  

С

1(21)

= {1, 2, 4, 8, 16, 11} 

С

3(21)

= {3, 6, 12} 

С

5(21)

= {5, 10, 20, 19, 17, 13} 

С

7(21)

= {7, 14} 

С

9(21)

= {9, 18, 15} 

С

0(63)

= {0 = 63} 

С

3(63)

= {3, 6, 12, 24, 48, 33} 

С

9(63)

= {9, 18, 36} 

С

15(63)

= {15, 30, 60, 57, 51, 39}  

С

21(63)

= {21, 42} 

С

27(63)

= {27, 54, 45} 

Таким  образом,  найдены  все  неприводимые  многочлены,  входящие  в 

разложение х

63

+1 с порядком корней, меньшим 63. 

В  качестве  представителей  циклотомических  классов  s  используют 

наименьшие числа в классе. При построении циклотомических классов они 
выбираются как минимальные числа, не вошедшие в предыдущие классы. 
Представители циклотомических классов используются в качестве первого 
подстрочного индекса в обозначении класса. 

Вид многочленов, соответствующих циклотомическим классам, в рас-

смотренном примере взят из таблиц неприводимых многочленов над полем 
GF(2),  представленных  в  [1]  (таблицы  в  усеченном  виде  даны  в  приложе-
нии). Неприводимые многочлены расположены по степеням m. 

Число m определяет степень расширения поля GF(2

m

), элементами ко-

торого являются корни представленных многочленов. Под числом m пока-
заны  все  неприводимые  многочлены  со  степенями,  делящими  m,  кроме 
многочлена х+1. 

Для  многочлена  указана  характеристика  в  виде  цифры,  являющейся 

представителем  циклотомического  класса,  соответствующего  указанному 
многочлену по модулю 2

m

–1, и латинской буквы (только для многочленов 

степени m), несущей следующую информацию о многочлене: 

 
A, B, C, D 

– 

непримитивный 

E, F, G, H 

– 

примитивный 

A, B, E, F  

– 

корни линейно зависимы 

C, D, G, H 

– 

корни линейно независимы 

A, C, E, G 

– 

корни двойственного многочлена линейно зависимы 

B, D, F, H 

– 

корни двойственного многочлена линейно независимы. 

Из  двойственных  многочленов  в  таблице  (см.  приложение)  представ-

лен лишь тот, у которого представитель циклотомического класса меньше 
по  величине.  Многочлены  даны  в  двоично-восьмеричном  представлении. 
Каждый  символ  в  таблице обозначает три  двоичных  знака  в  соответствии 
со следующим кодом: 0 = 000, 1 = 001, 2 = 010, 3 = 011, 4 = 100, 5 = 101,  
6 = 110, 7 = 111. 

Коэффициенты  многочленов  расположены  в  порядке  убывания,  т. е. 

коэффициент при старшей степени расположен слева. 

Например, первый многочлен при степени 6 записан в виде: 1 103 F. В 

двоичной  записи  числу  103  эквивалентно  число  001000011,  и  соответст-
вующий многочлен равен х

6

+х+1. Буква F означает, что многочлен прими-

тивный,  его  корни  линейно  зависимы,  а  корни  двойственного  многочлена 
линейно независимы. Цифра, стоящая перед двоично-восьмеричным пред-
ставлением многочлена (в приведенном примере это 1), есть представитель 

циклотомического класса этого многочлена по модулю х

2

1

m



−1 (в примере 

по модулю х

63

+1). 

При  вычислении  порядка  корней  е  неприводимого  многочлена  или, 

что то же самое – показателя, к которому принадлежит данный многочлен, 
полезны данные табл. 2.4.2.  

Таблица 2.4.2 

Разложение 2

m

−1 на простые сомножители 

2

3

 − 1= 7 

2

4

 − 1= 3×5 

2

5

 − 1= 31 

2

6

 − 1= 3×3×7 

2

7

 − 1= 127 

2

8

 − 1= 3×5×17 

2

9

 − 1= 7×73 

2

10

− 1− = 3×11×31 

2

11

− 1= 23×89 

2

12

− 1= 3×3×5×7×13 

2

13

− 1= 8191 

2

14

− 1= 3×43×127 

2

15

− 1= 7×31×151 

2

16

−1= 3×5×17×257 

2

17

−1= 131071 

2

18

−1= 3×3×3×7×19×73 

2

19

− 1= 524287 

2

20

− 1= 3×5×5×11×31×41 

2

21

− 1 = 7×7×127×337 

2

22

− 1= 3×23×89×683 

2

23

− 1= 47×178481 

2

24

− 1= 3×3×5×7×13×17×241 

2

25

− 1= 31×601×1801 

2

26

− 1= 3×2731×8191 

2

27

− 1= 7×73×262657 

2

28

− 1= 3×5×29×43×113×127 

2

29

− 1 = 233×1103×2089 

2

30

− 1= 3×3×7×11×31×151×331 

2

31

− 1= 2147483647 

2

32

−1= 3×5×17×257×65537 

2

33

−1= 7×23×89×599479 

2

34

−1= 3×43691×131071 

2.5. Алгоритм разложения х

n

+1 на неприводимые сомножители 

Обобщением  вышеизложенного  в  отношении  разложения  двучлена 

вида  х

n

+1  на  неприводимые  над  двоичным  полем  сомножители  представ-

лено  в  виде приведенного  алгоритма, применение которого  проиллюстри-
руем двумя примерами. 

Пример  2.5.1.  Разложить  х

21

+1  на  неприводимые  сомножители  над 

GF(2). 

Шаг 1. Задано значение степени двучлена n =21.  
Шаг  2.  Заданное  значение  n  =21  не  может  быть  представлено  в  виде  

n =2

m

–1.  

Шаг 3. Из табл. 2.4.2 находим ближайшее к 21 число, которое делится 

на 21 и может быть представлено в виде 2

m

–1. Таким числом является 63, 

т. е. η = 63 и m = 6. 

Шаг  4.  Неприводимые  сомножители  х

21

+1  были  рассмотрены  в  при-

мере 2.4.1. Как они были определены? Число 21=3×7. Это означает, что в 
разложение  х

21

+1  входят  неприводимые  сомножители  двучленов  х

3

+1  и 

х

7

+1. Порядок их корней – 3 и 7 соответственно. Кроме того, х

21

+1, безус-

ловно, имеет корни порядка 21.  

Шаг 5. Число корней порядка 3 равно φ(3) = 2, порядка 7 – φ(7) = 6 и 

порядка 21– φ(21)=φ(3)×φ(7) =2×6= 12. 

Шаг 6. Итак, двучлен х

21

+1 имеет корни различного порядка. 

Шаг 7. Помимо х+1 в разложение х

21

+1 входят:  

- многочлен степени 2 с корнями порядка 3, 
- 2 многочлена степени 3 с корнями порядка 7.  

Новое значение η=2

6

–1 позволяет определить, что 12 корней порядка 21 

принадлежат двум многочленам степени 6. 

Итак, в разложение х

21

+1 входят следующие неприводимые сомножи-

тели: по одному степеней 1 и 2 и по два – 3 и 6. 

Шаг 8. Строим циклотомические классы по модулю 21 и преобразуем 

их представителей по модулю η=2

6

–1: 

{1, 2, 4, 8, 16, 11} 



{3,…}, 

{3, 6, 12}



{9,…}, 

{5, 10, 20, 19, 17, 13} 



{15,…}, 

{7, 14}



{21,…}, 

{9, 18, 15}



{27, …}. 

Шаг 9. В разложение х

21

+1 входят двойственные многочлены степеней 

3 и 6.