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

2. МНОГОЧЛЕН 

1,

n

x



 ЕГО КОРНИ  

И НЕПРИВОДИМЫЕ СОМНОЖИТЕЛИ 

2.1

. 

Связь между корнями x

n

–1 и элементами поля GF(q

) 

Многочлен  x

n

–1,  его  неприводимые  сомножители  и  их  корни  играют 

существенную  роль  в  построении  важнейшего  класса  групповых  кодов  – 
циклических  кодов.  Знание  корней  сомножителей  x

n

−1  позволяет  решить 

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

Рассмотрим общий случай. Пусть x

n

–1 задан над полем GF(q). Извест-

но, что GF(q) имеет циклическую группу из q–1 своих ненулевых элементов. 

Порядок каждого ненулевого элемента GF(q) не может быть выше q–1, 

а это означает, что α

q−1

=1 для любого ненулевого элемента α из GF(q), т. е. 

любой ненулевой элемент GF(q) обращает x

q−1

–1 в нуль, а значит, является 

его корнем. Поскольку x

q−1

–1 имеет ровно q–1 корней, следовательно, все 

ненулевые элементы GF(q) являются корнями x

q−1

–1. 

Таким  образом,  имеется  однозначное  соответствие  между 

корнями x

q

−1

–1 и ненулевыми элементами GF(q). 

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

нями из расширенных полей Галуа GF(2

m

).  

В соответствии с полученным результатом справедливо утверждение – 

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

m

) 

являются корнями 





2

1

1

m

x

. 

Важно  уметь  сопоставлять  совокупности  элементов  GF(q),  в  частном 

случае  GF(2

m

),  с  корнями  неприводимых  сомножителей  х

q–1

−1  (в  двоичном 

случае с корнями 

2

1

1

m

x





), ровно как и с корнями х

n

−1 при произвольном n. 

При выявлении сомножителей х

n

−1 полезны следующие свойства, ха-

рактеризующие  связи  между  элементами  GF(q),  и  многочленами,  являю-
щимися делителями х

n

−1. 

Свойство  1.  Наличие  в  двучлене  х

n

−1  сомножителей  вида  х

m

−1,  где 

m<n. Пусть n=m×d, где n, m и d – целые положительные числа. Рассмотрим 
двучлен у

d

−1. Очевидно, что при у=1, он обращается в нуль, и 1 является 

корнем у

d

−1. 

Тогда по теореме Безу у

d

−1 делится на у–1. Положим, что у=х

m

. Тогда, 

очевидно, х

md

−1 делится на х

m

−1. 

Таким образом,  справедливо следующее: многочлен х

n

−1 делится 

на многочлен х

m

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

Свойство 2. Поля Галуа GF(p

m

), образованные классами вычетов мно-

гочленов  по  модулю  примитивного  неприводимого  над  полем  GF(p)  мно-

гочлена  π(x)  степени  m,  называют  полями  характеристики  р  при  любом

выборе m. В поле GF(p) элемент p=0. 

В поле характеристики p для любых чисел a и b справедлива биноми-

нальная теорема:  

1

1

2

2 2

(

)

...

,

p

p

p

p

p

p

p

a

b

a

C a

b C a

b

b















где 

!

!(

)!

i

p

p

Ñ

i p

i





 – биноминальные коэффициенты. 

Поэтому  справедливо:  в  поле  характеристики  p  имеет  место 

равенство (a+b)

p

 = a

p

+b

p

. 

Свойство 3. Пусть многочлен f(x)=a

0

 +a

1

 x+...+a

m

 x

m

 степени m непри-

водим в поле GF(p). Рассмотрим (f(x))

p

. 

По предыдущему свойству: 

(f(x))

p

 = (а

0

)

p

+(a

1

x

1

)

p

+...+(a

m

 x

m

)

p

= а

0

p

+ a

1

p

(x

p

)+...+ a

m

p

(x

p

)

m

= 

= а

0

+a

1

(x)

p

+...+a

m

 (x

р

)

m

 = f(x

p

). 

Этот  результат  получен  в  силу  того,  что  для  любого  элемента  a

i

  из 

GF(p) справедливо: 

1

1

p

i

a





 и 

.

p

i

i

a

a



Пусть β − корень f(x), тогда f(β) = 0. 
В силу полученного результата (f(β))

p

= f(β

p

) = 0, т. е. для любого кор-

ня β многочлена f(x) справедливо утверждение, что β

p

 также является кор-

нем  f(x).  Так  как  неприводимый  многочлен  f(x)  степени  m  имеет  всего  m 
корней и один из его корней есть β, то m степеней β от р

0

=1 до p

m–1

 явля-

ются корнями f(x). 

Таким  образом,  справедливо:  если  f(x)  –  многочлен  степени  m  с 

коэффициентами  из  поля  GF(p),  неприводимый  в  этом  поле,  и  

β – корень f(x), то β, β

p

, …, 





1

m

p

– все корни f(x). 

Свойство 4.

Прямым следствием из свойства 3 является следующее. 

Все  корни  неприводимого  многочлена  имеют  один  и  тот  же 

порядок. 

Для доказательства этого свойства предположим, что корнями некоторо-

го неприводимого многочлена f(x) степени m являются β, имеющий порядок e, 

и 

1

m

p





, имеющий порядок  l. Тогда ((

)

(

)

1

,

j

j

j

p

e

e p

p



 



  и  поэтому  e  де-

лится на l. Аналогично, 

(

)

((

) )

1

1,

m

j

m j

j

m j

l

p

l

p p

l

p

l p

m j

p







  

 

 





 так 

что l делится на e. Поскольку e и l – целые положительные числа, значит e = l, 
что и доказывает свойство 4. 

Свойство 5.

Выше показано однозначное соответствие между ненуле-

выми элементами GF(p

m

) и корнями двучлена 

1

m

p

x



. Определим вид мно-

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

m

).  Пусть  

α – произвольный элемент поля порядка p

m

–1.  

Тогда  справедливо: 

,

m

p



 

  т. е.  α  является  корнем  уравнения 

0.

m

p

x

x

 

Данный  результат  известен  в  литературе  как  теорема  Ферма:    любой 

элемент α поля GF(p

m

) удовлетворяет тождеству 

m

p



 

 или эквива-

лентно является корнем уравнения

0.

m

p

x

x

 

Следствием  теоремы  Ферма  является  тот  факт,  что  двучлен 

m

p

x

x



может  быть  представлен  в  виде  произведения  p

m

  сомножителей  следую-

щим образом: 

1

(

),

m

m

p

p

i

i

x

x

x

a



  



где a

i

= GF(p

m

), т. е. все элементы a

i

 или GF(p

m

) являются корнями двучлена 

m

p

x

x



, причем каждый корень встречается только один раз. 

Элемент поля GF(p

m

) α порядка p

m

 –1 называется примитивным и лю-

бой ненулевой элемент поля является степенью α, т. е. для ненулевых эле-
ментов a

i

 справедливо a

i

 = α

i

, где i принимает значение от 1 до p

m

 –1. 

Свойство 6. Свойство 3 устанавливает связь между корнями неприво-

димого  многочлена  f(x).  Естественно  считать,  что  корень  f(x)  –  элемент 
расширенного  поля  GF(p

m

).  Какой  может  быть  максимальная  степень  не-

приводимого многочлена с корнями из GF(p

m

) или что то же самое – какова 

максимальная степень неприводимого сомножителя 

m

p

x

x



? 

Ответ на этот вопрос дает анализ возможной максимальной степени в 

последовательности корней: 

2

1

,

,

,

.

m

p

p

p



 





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

корня  через  примитивный  элемент  поля 



GF(p

m

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

выше  последовательность  корней  однозначно  соответствует  последова-
тельности степеней примитивного элемента: 

1

2

3

{ ,

,

,

,...,

},

s

m

s

ps

p s

p s

p

s



где m

s

 – наименьшее положительное число такое, что 

s

m

p

×s = s по модулю 

p –1. 

Модуль  p

m

–1  отражает  порядок  примитивного  элемента  поля.  В  по-

следовательности степеней корней следующая степень 

.

m

p



 

Максимальная  степень  неприводимого  многочлена  в  разложе-

нии 





1

1

m

p

x

, 

равно как и в разложении многочлена 

m

p

x

равна m. 

Последовательность, взятая в фигурные скобки, получившая название 

циклотомического  класса,  в  зависимости  от  значения  s  может  содержать  
m

s 

≤ m элементов. Число s, стоящее в начале циклотомического класса, по-

лучило название образующего или представителя циклотомического клас-
са.  Ниже  будет  показано,  что  число  элементов  в  циклотомическом  классе  
m

s 

должно быть делителем числа m. 

Справедливо  следующее:  множество  целых  чисел,  отображаю-

щих  степени  примитивного  элемента  α  поля  GF(p

m

) 

в  представ-

лении ненулевых элементов поля в виде циклической группы, рас-
падается на подмножества, называемые циклотомическими клас-
сами  по  модулю  p

m

–1.  Каждый  циклотомический  класс  однозначно 

соответствует одному из неприводимых сомножителей 





1

1

m

p

x

. 

Понятно,  что:  полное  число  циклотомических  классов  для  поля 

GF(

p

m

) 

совпадает  с  числом  неприводимых  сомножителей  много-

члена 





1

1

m

p

x

,

и  множество    элементов,  охватываемых  цикло-

томическими классами, отображает все ненулевые элементы по-
ля GF(p

m

). 

Например,  циклотомическими  классами  по  модулю  15  для  p=2  явля-

ются: 
С

0(15)

={0}, C

1(15)

={1,2,4,8}, C

3(15)

={3,6,12,9}, C

5(15)

={5,10}, C

7(15)

={7,14,13,11}, 

здесь  С

s(15) 

обозначает  циклотомический  класс  по  модулю  15,  начинаю-

щийся с числа s. 

Анализ приведенных последовательностей означает, что двучлен x

15

+1 

над  полем  GF(2)  состоит  из  5  неприводимых  сомножителей:  одного  со-
множителя 1-й степени с корнем порядка 1, одного сомножителя 2-й степе-
ни  с  корнем  порядка  3  и  трех  сомножителей  степени  4,  два  из  которых 
имеют порядок корней 15, а один – имеет порядок корней 5.  

Результаты  этого  анализа  показывают,  что  последовательность  C

0(15) 

соответствует  многочлену  x+1;  последовательность  C

5(15) 

соответствует 

многочлену 2-й степени с корнями порядка 3 – это многочлен х

2

+х+1 – не-

приводимый  сомножитель  двучлена  х

3

+1;  последовательность  C

3(15) 

соот-

ветствует 

неприводимому 

сомножителю 

4-й 

степени 

двучлена 

х

5

+1=(x+1)(x

4

+ x

3

+

x

2

+x+1), отсюда и порядок корней, равный пяти.  

Многочлены, соответствующие последовательностям C

1(15)

 и C

7(15)

, мо-

гут быть найдены на основе теоремы Безу: 

f

1

(x)=(x+α))(x+ α

2

))(x+α

4

))(x+α

8

), 

f

7

(x)=(x+α

7

)(x+α

11

)(x+α

13

))(x+α

14

).

Анализ многочленов f

1

(x) и f

7

(x) будет выполнен далее. 

Свойство  7.  Анализ  неприводимых  многочленов,  входящих  в  разло-

жение 

4

2

1

1,

x





  имеющих  корни  среди  элементов  GF(2

4

)  показывает,  что 

степени  всех  неприводимых  многочленов:  1,  2,  4  являются  делителями 
числа 4. Обобщим этот результат следующими рассуждениями.

Пусть  f(х)  –  неприводимый  сомножитель  степени  d  ≤  m  многочлена 

m

p

x

x



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

d

–1 поля GF(p

m

), являющийся прими-

тивным элементом подполя GF(p

d

) поля GF(p

m

), принадлежит циклической 

группе  GF(p

m

)  порядка  p

m

–1.  Следовательно,  p

d

–1  делит  p

m

–1,  а  это  воз-

можно только в том случае, когда d делит m.  

Значит,  справедливо:  для  простого  числа  р  многочлен 



m

p

x

x  

равен  произведению  всех  нормированных  неприводимых  над  GF(p) 
многочленов, степени которых делят m. 

Свойство  8.  Аналогичные  рассуждения  приводят  к  следующему  ут-

верждению:  для  любого  поля  GF(q),  где  q=р

m

  (

степень  простого 

числа) имеет место равенство: 



m

p

x

x  равно  произведению  всех 

нормированных неприводимых над GF(p) многочленов, степени ко-
торых делят m. 

Свойство 9. Рассмотрим подробнее многочлены над GF(2): 

f

1

(x) = (x+α)(x+α

2

)(x+α

4

)(x+α

8

), 

f

7

(x) = (x+α

7

)(x+α

11

)(x+α

13

)(x+



14

). 

Корни этих многочленов являются элементами поля  GF(2

4

), с учетом 

правил сложения и умножения в этом поле простым умножением находим: 

f

1

(x) = 1+x+x

4

, 

f

7

(x) = 1+x

3

+x

4

. 

Многочлены f

1

(x) и f

7

(х) относятся к двойственным (взаимным) много-

членам. 

Многочлен f

*

(x),  двойственный  некоторому  многочлену  f  (x),  опреде-

ляется как f

*

(x) =х

m

 f(1/х), где m – степень f(x). 

Для двойственных многочленов f

*

(x) и f(x) справедливо: 

1) корни f

*

(x) обратны корням f(x); 

2) многочлен f

*

(x) неприводим тогда и только тогда, когда неприводим f(x);