Единственный не тождественно нулевой вектор, удовлетворяющий условиям (3.36), имеет координаты W3 = т( = то = 1, W2 = О, т. е.Л/= (1 О 1 1) и минимальный полином т(х) = ms (х) = + X + i,

Аналогично для элемента (3=4, взятого из другого циклокласса поля GF(2), я(х) = х +Х+ 1, получим

тз то

где переход к последней матрице осуществлен за счет суммирования третьего столбца с двумя другими в предьщущей матрице. Следовательно, тз + т2=0, mi = = О, тз + mo = О, откуда тз = т2 = то = 1, mj = О, т. е.Л/ = (1 1 О 1) и т4 (х) =

= х + X + i.

Рассмотрим более сложный пример для элемента (3= 86 поля GF(2 ), п(х) = X* + х** + х + 1. Пользуясь табл. 3.7, составим матрицу

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

Следовательно, т2 + т = О, тг +то= 0; откуда тг = =то = 1 и т85(х) = = х + х+ 1.

Другой универсальный метод отыскания минимального полинома т(х) элемента (3 основан на соотношении (3.32) и предполагает, что не только поле GF(2) уже построено, но и его элементы разбиты на циклоклассы (или хотя бы найден циклокласс для элемента р). Пусть, например, задано поле GF(2 ), я(х) = X® + х** + х + х + 1 - см. табл. 3.7 и необходимо найти полином т2-Из табл. 3.14 видно, что элемент = 52 находится в циклоклассе {52, 103, 205, 154 I . Воспользовавшись соотношением (3.32) и теоремой Виета, получим

Ws2() = (х+52) (х+ 103) (х+ 205) (х+ 154) =

г

= х** + (52 + 103 + 205 + 154)х + (52 • 103 + 52 • 205 + 52 • 154 +

+ 103 • 205 + 103 • 154 + 205 154)х + (52- 103 • 205 +52 • 103 • 154 +

+ 52- 205 154+ 103 • 205 • 154)х + 52 • 103 • 205 • 154 = х** + х + х + х+ 1,

так как согласно формуле (3.23) и табл. 3.7 для используемого поля справедлив! соотношения:

5 - 1610

52-103 52-205 52-154

103 - 205 103 • 154 205 - 154

154 1

205 52 1

1 0 0 1 0 0 1 0

0 0 0 0 0 0 0 1

110 1110 1

0 0 0 0 1 0 1 0

0 0 0 0 0 0 0 1

0 1 0 0 0 1 0 0

0 0 0 0 0 0 0 1

52 52 52 103

103 103 205 205

205 154 154 154

103 52 154 205

0 1 0 0 0 1 0 0

0 0 0 0 1 0 1 0

1 0 0 1 0 0 1 0 110 1110 1

0 0 0 0 0 0 0 1

следовательно, 52 + 103 + 205 + 154 = 1, а также 52 - 103 - 205 • 154 = 1.

Число циклокласоов неприводимых и минималы1ых полииомов. Подсчет

числа неприводимых над полем GF (2) и, следовательно, минимальных полиномов степени i может быть осуществлен по формуле [8]

(3.37)

где м(/) - функция Мебиуса, определяемая соотношениями (3.34), а суммирование ведется по всем (делителям i числа /, включая 1 и само /. Например, 1=6 имеет делители i { 1» 2, 3, в] , следовательно, м(1) = 1, м(2) = -1, м(3) =-1,

J(6) = (-1)2= 1. Поэтому/б = (2*

2" + 2) : 6 = 9.

Число неприводимых полиномов степени / совпадает с числом циклокласоов длины /. Это позволяет вывести рекуррентную формулу для If. Пусть / делится на /о = 1, i. • - •» jt 1, lie Тогда

7

i - А: - 1 i = О

(3.38)

В частном случае, когда / - простое число, из выражений (3.37) и (3.38) следует

А (2

-2), 2<1 - простое число.

Если / = 2 - степень числа 2, то

/. =

*

i = О

21 V

Так, для / = 1 из в: муле учтено, что b

S (... ) =0 при b < а а

(3.37) и (3.38) следует/i =2; в последней фор-

Таблица 3.15

Количество циклоклассов Ir (минимальных и неприводимых полиномов) и нормальных базисов

для полей GF(2)