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

выборе коэффициентов многочлена из поля GF(q) равен q

n

. При q=2 число 

классов вычетов многочленов по модулю многочлена степени n равно 2

n

. 

При  выборе  в  качестве  образующего  класса  вычетов  многочлена  ми-

нимальной степени в своем классе, как это сделано в примере, поясняющем 
кольцо многочленов по модулю x

2

+1, образующими классов вычетов будут 

все возможные многочлены степеней от нулевой (единица) до n–1. 

В кольце, которое образуют классы вычетов, также может быть найден 

идеал  как  множество  классов  вычетов  с  образующими,  кратными  некото-
рому многочлену g(x), степень которого, естественно, меньше n. 

Многочлен g(x) минимальной степени, отличный от нуля, та-

кой,  что  класс  вычетов  {g(x)}  образует  идеал  I,  содержащий  все 
классы  вычетов,  кратные  {g(x)},  в  кольце  многочленов  по  модулю 
f(x

) тогда и только тогда, когда g(x) является делителем f(x). 

Действительно, в соответствии с алгоритмом деления 

{f(x)}={0}={g(x)}{q(x)}+{r(x)}, 

где q(x) – частное от деления f(x) на g(x), r(x) – остаток от деления.  

В  соответствии  с  представленной  записью  {r(x)}  принадлежит  идеа-

лу{0}, и при этом  r(x) имеет степень меньшую, чем степень  g(x), что воз-
можно лишь в том случае, когда r(x)=0. 

Определим размерность идеала в кольце многочленов по модулю мно-

гочлена  f(x)  степени  n,  если  идеал  образован  всеми  кратными  некоторого 
многочлена g(x), являющегося делителем f(x). 

Пусть f(x)=g(x)h(x), где h(x) – многочлен степени к, а f(x) имеет степень n. 
Многочлены вида x

0

g(x),x

1

g(x),..., x

к–1

g(х) линейно независимы и при-

надлежат идеалу, а их линейная комбинация  

s(x) = (a

0

 x

0

+…+а

к–1

x

к–1

) g(x), 

где  а

i 

–  элемент  основного  поля,  отлична  от  нуля,  так  как  имеет  степень, 

меньшую n, и также принадлежит идеалу.  

Значит,  идеал,  порожденный  многочленом  g(x)  степени  n–k, 

являющийся  делителем  f(x)  степени  n,  в  кольце  многочленов  по 
модулю f(x) имеет размерность, равную k. 

Пример  1.3.1.  Рассмотрим  кольцо  многочленов  по  модулю  

f(x) = x

3

+1= =(x+1)(x

2

+x+1).  

Это кольцо содержит следующие классы вычетов:  

{0}, {1}, {x}, {1+x}, {x

2

}, {1+x

2

}, {x+x

2

}, {1+x+x

2

} 

или {000}, {100}, {010}, {110}, {001}, {101}, {011}, {111} . 

В данном кольце возможны два идеала. 
I

1

, порожденный {x+1}; общий вид элемента идеала: 

{(a

0

 x

0

+a

1

 x

1

)(x+1)}; размерность 2; при подстановке a

i

=0 или 1 имеем 

{0}, {1+x}, {1+x

2

}, {x+x

2

} или {000}, {110}, {101} и {011}. 

I

2

,  порожденный  {x

2

+x+1}.  Размерность  1.  Включает  классы  вычетов 

{0} и {1+x+x

2

} или {000} и {111} в двоичном представлении. 

1.4. Поля Галуа. Мультипликативная группа поля Галуа 

В  п.  1.1  дано  аксиоматическое  определение  поля,  введены  понятия  и 

приведены примеры простого и расширенного полей. Обобщением сказан-
ного в п. 1.1 и 1.3 являются следующие определения [1, 2]. 

Для простых полей – кольцо классов вычетов по модулю m явля-

ется полем тогда и только тогда, когда m – простое число. 

Для  расширенных  полей  –  кольцо  многочленов  по  модулю  неко-

торого  неприводимого  в  поле  GF(p)  многочлена  π(x)  степени  m 
является полем GF(p

m

). 

К  многочлену  π(x)  кроме  требования  неприводимости  предъявляется 

еще одно принципиальное требование – ненулевые элементы поля являют-
ся степенями корня α многочлена π(x). 

Если  ненулевые  элементы  поля  GF(m)  могут  быть  представлены  как 

степени  некоторого  элемента  α,  то  α  называют  примитивным  элементом 
этого поля.  

Неприводимый многочлен степени m над полем GF(p) называ-

ется  примитивным,  если  его  корнем  является  примитивный  эле-
мент GF(p

m

). 

В п. 1.1 было показано, что поле GF(2

2

) в качестве ненулевых элемен-

тов имеет 1, α, 1+α, где α – корень π(x)=1+x+x

2

,  т. е.  1+α+α

2

=0.  Поскольку 

1=α

0

, а 1+α=α

2

, все ненулевые элементы GF(2

2

) представляются степенями 

корня  π(x)  .Элемент  α  является  примитивным  элементом  GF(2

2

),  а 

π(x)=1+x+x

2

 является примитивным неприводимым многочленом. 

Рассмотрим поле GF(5). Поскольку 5 – простое число, то кольцо клас-

сов вычетов по модулю 5 образует поле GF(5).Таблицы сложения и умно-
жения по модулю 5 приведены в п.  1.3. Для этого поля также  существует 
примитивный элемент, степени которого дают все ненулевые элементы по-
ля, например 2

0

=1; 2

1

=2; 2

2

=4; 2

3

=8=3; 2

4

=16=1; 2

5

=32=2. 

Эти примеры могут быть обобщены следующим образом. В любой ко-

нечной  мультипликативной  группе  можно  рассмотреть  совокупность  эле-
ментов, образованную некоторым элементом g и его степенями g

2

, g

3

 и т. д.  

Группа имеет конечное число элементов, поэтому неизбежно появится по-
вторение, т. е. для некоторых i и j будет g

i

 = g

j

 . 

Если  наблюдается  g

i

=g

j

,  то  g

j−i

=1.  Следовательно,  некоторая  степень 

элемента g равна 1. Пусть e – наименьшее положительное число, при кото-

ром g

e

=1. Совокупность элементов 1, g, g

2

,  ...,  g

e−1

образует подгруппу по 

операции  умножения,  так  как  налицо  единичный  элемент  1,  замкнутость, 
наличие обратных элементов: для g

i

 обратный элемент g

e−i

.  

Группа, состоящая из всех степеней одного из ее элементов, получила 

название циклической группы. Число e называется порядком элемента g. 

Обобщением изложенного выше является следующее. 
В  поле  GF(q)  существует  примитивный  элемент  α,  т.е.  эле-

мент  порядка  q–1.  Каждый  ненулевой  элемент  поля  GF(q)  может 
быть  представлен  как  некоторая  степень  α,  т. е.  мультиплика-
тивная группа поля Галуа GF(q) является циклической. 

Если  мультипликативная  группа  порядка  q  содержит  циклическую 

подгруппу из e элементов, порожденную некоторым элементом g, то число 
смежных  классов  в  разложении  группы  по  циклической  подгруппе  будет 
равно q/e, и каждый смежный класс  также будет содержать e элементов. 

Значит справедливо следующее утверждение. 

Порядок  e  любого  элемента  группы  является  делителем  по-

рядка  группы.  Число  элементов  поля  GF(q

m

)

,  имеющих  порядок  e, 

определяется выражением: Ne = φ(e), 

где φ(e) – функция Эйлера [3], равная числу чисел взаимно простых с  e и 
меньших e.  

Функция Эйлера может быть вычислена следующим образом. 

Если e – составное число вида 

1

i

t

l

i

i

e

p







, где p

i

 > 1 – простое, а l

i

 – на-

туральное число и i = 1,2, ..., t,  

то φ(e) = 

1

1

1

1

1

( )

(

1)

(1

)...(1

)

i

t

l

i

i

t

i

e

p

p

å

p

p









 







. 

В частности, для простого р и целого а 

φ(р

а

)= р

а

 − р

а–1

, φ(р) = р – 1. 

Кроме того, φ(а

1

×а

2

) = φ(а

1

)φ(а

2

), если а

1

и а

2

взаимно просты. 

Например: 

φ(1) = 1 

φ(4) = 2 

φ(2) = 1 

φ(5) = 4 

φ(3) = 2 

φ(6) = 2 

Пример  1.4.1.  Определить  число  элементов  N

i

  поля  GF(

2

6

)  порядка  

i = 1, 3, 7, 9, 21, 63.

Решение: N

i

= 

φ

(i),  где  φ(i)  –  функция  Эйлера,  для  вычисления  кото-

рой  необходимо  знать  каноническое  разложение  числа  i:  1=1,  3=3,  7=7, 
9=3

2

, 21=3×7, 63=3

2

×7. 

Теперь находим: N

1

 = φ(1) = 1, N

3

 = φ(3) = 2, N

7

 = φ(7) = 6, N

9

 = φ(9) = 

=9(1−1/3) = 9×2/3 = 6, N

21

 = φ(21) = 21(1−1/3)(1−1/7) = 21×2/3×6/7 = 12, или 

φ(21)=φ(3)φ(7)=2×6=12, N

63

 = φ(63) = 63(1−1/3)(1−1/7) = 63×2/3×6/7 = 36. 

Рассмотренные числа 1, 3, 7, 9, 21, 63 являются делителями числа 63 и 

поэтому  определяют  все  возможные  порядки  элементов  мультипликатив-
ной группы поля GF(2

6

).  

Полученный результат может быть обобщен следующим образом. 
Сумма всех ненулевых элементов поля GF(q) с различными по-

рядками равна порядку его мультипликативной группы q–1. 

Важным следствием из рассмотренного является следующее. 
Пусть 



  –  примитивный  элемент  GF(p

m

),  порядок  которого  равен 

1

m

p



, т. е. 

1

1.

m

p







Если среди элементов поля GF(p

m

) есть элемент β порядка p

r−1

, где r < m, 

т. е. 

1

1

,

m

r

p

p





  

  то  последовательность  элементов  β

1

,  β

2

,  …, 

1

r

p





=

1

m

p





образует  циклическую  подгруппу  мультипликативной  группы  GF(p

m

),  

т. е.  содержит  все  ненулевые  элементы  нового  поля  GF(p

r

),  являющегося 

подполем GF(p

m

). 

Итак, GF(p

m

) 

содержит подполе GF(p

r

)

, если p

r

–1 делит p

m

–1. 

В п. 2.1 будет показано, что p

r

−1 делит p

m

−1, если r делит m.  

Таким образом, окончательно 

GF(p

m

) 

содержит подполе GF(p

r

)

, если r делит m. 

Пример 1.4.2. Рассмотрим подполя поля GF(2

12

). Число 12 делится на 

числа 6, 4, 3 и 2, т. е. в составе поля GF(2

12

) существуют в качестве подпо-

лей поля GF(2

6

), GF(2

4

), GF(2

3

), GF(2

2

).  

Любое расширенное поле содержит основное поле, поэтому в каждом 

из  указанных  полей  содержится  поле  GF(2).  Найдем  циклические  группы 
рассматриваемых полей. Обозначим примитивные элементы  полей: 

GF(2

12

)→ α, GF(2

6

) → β, 

GF(2

4

) → γ, GF(2

3

) → δ, 

GF(2

2

) → ε, GF(2) → ζ. 

Выразим ненулевые элементы полей через степени примитивных эле-

ментов: 

GF(2

12

): α

1

, α

2

, α

3

, …

, α

4095

α

12 1

2



=1, е = 4095 

GF(2

6

): β

1 

, β

2

 ,β

3

 ,… , β

63

β

6 1

2



=1, е = 63 

GF(2

4

): γ

1

, γ

2

, γ

3

, … , γ

15

γ

4 1

2



=1, е = 15 

GF(2

3

): δ

1

, δ

2

, δ

3

 , … , δ

7

δ

3 1

2



=1, е = 7 

GF(2

2

): ε

1

, ε

2

, ε

3

ε

2 1

2



=1, е = 3 

GF(2): ζ

1

ζ

1 1

2



=1, е = 1 

 
Элементы полей GF(2

6

), GF(2

4

), GF(2

3

), GF(2

2

) и GF(2) входят в состав 

GF(2

12

), при этом β = α

65

, так как β

63

 = α

4095

 = 1 = (α

65

)

63

 . Аналогично γ = α

273

, 

δ = α

585

, ε = α

1365

, ζ = α

4095

.  

 
Связь между рассмотренными полями иллюстрирует рис. 1.1 [2, 4]. 

Рис.1.1. Поле GF(2

12

) и его подполя 

GF(2

12

) 

GF(2

6

) 

GF(2

4

) 

GF(2

3

) 

GF(2

2

) 

GF(2)