100000000000 010000000000 001000000000

eooioooooooo

000010000000 000001000000 000000100000 000000010000 000000001000 000000000100 000000000010 000000000001 111000111000 1 0 0 0 1 1 1 0 0 1 0 0 0 1 1 1 0 1 0 0 0 1 1 1 10 110 1 1 о 1 о о 1

10000000 0 000 001000000000 000010000000 00000010000О 00000000100 0 „ 000000000010 111000111000 00111000111О 1110 110 1

о 1 1

0 о 1

1 1 1 1 о о

10 10 1 0 10 10 110 0 1

о 1 о о

0 10 1 0 0 10 1 0 0 1 0 0 1 0 0 1110 0 10 0 1110

10101001001О 110010011100 001100100111

000000000000 011000000000 001010000000 000100100000 000010001000 000001000010 111000011000

1 0 0 1 0 0 1 1 1

0 0 1 1 1 0 0 1 1 1 1110 110 10 0 10 10 10 0 10 1

1 1 0 0 1 0 0 1 1 1 0 0 1 1 0 0 1 0 0 1

1 о 1 о

Если перенумеровать столбцы матрицы @ - J числами от О до 11 и прибавить третий столбец к шестому, первый, второй и четверты! столбцы к восьмому, а пятый столбец к десятому, то верхний правы! восьмимерный квадрат матрицы й - 3 можно сделать нулевыз* Нижний правый квадрат при этом примет вид

О 1 1 О .0 О 111110 О 1 1 О О 1 0 10 110 0 11110 0 0 1110

Решениями уравнения [е, т, g] М = являютс

[6, 8ъ , gii) = U, О, О, Л, О, А], где Л = О или 1. Перв1 шесть координат g легко находятся из уравнения g (б - J) = решения которого имеют вид g = [В, А, О, А, А, О, А, О, О, А, О, А\ где А, В GF (2). Наконец, применим алгоритм Евклида к / (ж) J = 1110001110001 и g{x)-s = si 0 110 10 0 10

Выбирая S независимой переменной и t - s + l, можно с помош;ью одних и тех же вычислений найти н. о. д. многочленов 1110001110001и010110100101ин. о. д. многочленов 111000111000 IHIIOIIOIOOIOI:

1110001110001 slOllOlOOlOl

liOOlllOlOl slOllOlOOlOl

sOflUOl UOOlllOlOl

ItOsisOl

somm mm

Если f = 0, TO H. o. Д. равен 10011101, если s = О, н. о. д. многочленов lllOOOlllOOOlnOlOllOlOOlOl равен н. о. д. многочленов 111101и11001001и совпадает с 1 1 1 1 О 1. Оба многочлена 111101и10011101 неприводимы над полем GF (2) и разложение является полным: 1 4- х + + а;б + ж + х» + х = (1 + х + х + з? + x) X X (1 + аг* + X* + -f- х).

в общем случае предположим, что/(а;) = [] [р() (x)f, где каждый

многочлен p<> (х) неприводим над GF (q). Многочлен / (х) делит и Ig {х) - s] тогда и только тогда, когда каждый многочлен (х)

делит g (х) - Si для некоторого s,- g GF (q). С другой стороны, для произвольного заданного множества скаляров s, sj, s3, . . ., 6 GF (q) китайская теорема об остатках 2.17 гарантирует существование единственного по mod / (х) многочлена g (х), такого, что g (х) = Si mod [p> {x)Vi для всех i. Так как существует точно gr" векторов {si, s2, . . ., Sn), то существует точно решений уравнения [g (х)]ч - g (х) ~0 mod / (х). Это доказывает

6.13. Теорема. Число различных неприводимых делителей f {х) равно размерности нуль-пространства матрицы й - J.

В частности, многочлен / (х) является степенью неприводимого многочлена тогда и только тогда, когда нуль-пространство матрицы g J имеет размерность 1. В этом случае решениями сравнения [g (х)]9 - g (х) = 0 mod / (х) являются только скаляры поля

iq) и нуль-пространство матрицы й - 0 содержит единственный вектор вида [s. О, О, . . ., 0]. Если размерность нуль-пространства

матрицы @ - J равна п, то оно имеет базис, состоящий из п нормированных многочленов g<i) (х), g-l (х), . . ., (х). Без потери общности можно считать, что g(> (ж) = 1 и что степени остальных {п - 1) многочленов положительны.

Применяя алгоритм Евклида к / (ж) и g() {х) - s, мы получим разложение / (ж). Если это разложение содержит менее п множителей, то вычисляем п. о. д. g{x) - s и каждого уже известного множителя многочлена /(х) и т. д. Следующие соображения показывают, что этот процесс приводит в конце концов к разложению / (х) в произведение степеней п неприводимых многочленов.

Пусть - некоторая {п X ?г)-матрица над GF [q), где (х) =

S eij mod {x)f. Тогда ё невырожденна, так как если Ajei,j = О для всех i, то Ajg (х) =0 mod [р<> {х)Р для

всех i и, следовательно, () = 0 mod / (х), что нротиворе-

чит линейной независимости g() (х), (х), . . ., g() (х). Так как в ;-м столбце матрицы ё стоят различные элементы, то, применяя к / (х) и (х) - S алгоритм Евклида, получим разложение / (х) на различные множители. Степени неприводимых многочленов [р()(х)]

и (х)]"выделяются тогда и только тогда, когда Так как IS невырожденна, то для каждых i и к существует некоторое /, такое, что ei,j "ek.j- Следовательно, некоторый многочлен: g< (х) выделяет степени любых дэух неприводимых делителей / (х).

Степень произвольного неприводимого делителя может быть; определена путем применения алгоритма Евклида к многочлензг / (х) и его производной.

Если д достаточно велико, то к этому алгоритму может быть применено несколько остроумных приемов, некоторые из которых обсуж даются во втором томе книги Кнута [1968].

*6.2. Определение периода многочлена

Часто нужно знать период многочлена / (х), т. е. наименьшее число /, для которого многочлен / (х) делит х - 1. Если / (х)-I неприводимый многочлен степени т над GF (q), то период / (х) равещ наименьшему общему кратному мультипликативных порядков ег( корней (оно делит число q™ - 1).

Найдем связь между периодом многочлена и периодами era неприводимых делителей. Предположим сначала, что /(х) - ненриво! димый многочлен с периодом п, и найдем период многочлена,[/ (х)]" Так как п - делитель числа qs.f - 1, то пфО mod р, где р характеристика поля GF {q). Так как период / (х) равен п, то / (а делит многочлен х - 1 тогда и только тогда, когда А; = О (mod га

6.2. Определение периода многочлена 161

Если к = р/> где 7 не делится на р, то х - i - (х - 1)". Многочлен х - 1 не имеет кратных корней, так как он делит xfl~ - 1, где т - мультипликативный порядок числа q по модулю /. Следовательно, каждый неприводимый делитель многочлена х - \ имеет кратность р\ Отсюда заключаем, что если неприводимый многочлен. / (х) имеет период п, то период многочлена [/ (х)]™ равен пр, где p - наименьшая степень числа р, такая, что р т.

Предположим теперь, что / (х) = [/<i) (х)]"Ч/() (х)]"" . . ., где /() (х) - различные неприводимые многочлены.

Так как х - 1 делит х - 1 тогда и только тогда, когда к делит N, то период / (х) равен наименьшему обш;ему кратному периодов многочленов [/" (х)]™, [/() (х)]™, .... Это число в свою очередь равно произведению наименьшего обш;его кратного периодов многочленов (х) на наименьшую степень числа р, такую, что р m,i для всех i.

Итак, имеет место

6.21. Т е о р е м а. Если / (х) = [][/*(х)]™*, где /<*() -

неприводимые многочлены с периодами Hi над полем GF (q) характеристики р, то период f (х) равен произведению наименьшего общего кратного чисел ni на такую наименьшую степень p числа р, что р т,-для всех i.

Таким образом, задача определения периода многочлена сводится к задаче определения периодов каждого из его неприводимых множителей. Каков наилучший метод определения периода п неприводимого многочлена / (х)? Если степень / (х) равна т, то п должно быть делителем числа д"* - 1, так что первый шаг сводится к разложению д"* - 1 =nii Д Pi - различные простые числа. Опре-

делив классы вычетов х""". mod / (х), можно узнать, входит ли в период пчисло pp. Эти вычисления могут быть выполнены путем перемножения подходящих комбинаций классов вычетов х, х,

Х9-, . . ., x«"~*mod / (х). Если х" 1 mod/(х), то период / (х) кратен числу рр, если же х = 1 mod / (х), то число

рр не входит в период / (х). В последнем случае надо проверить, кратен ли период / (х) числам рр", рр~, .... Эти выкладки надо провести для всех простых делителей числа д*" - 1.

Результаты этих вычислений сразу позволяют определить период п многочленов /(х).

6.22. Пример. Чему равна блоковая длина укороченного циклического двоичного кода с порождающим многочленом g (х) =

= х» + ж 4- 1?

11-658