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

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

Найдем связь между периодом многочлена и периодами его неприводимых делителей. Предположим сначала, что неприводимый многочлен с периодом и найдем период многочлена Так как делитель числа то где характеристика поля Так как период равен то делит многочлен тогда и только тогда, когда

Если где не делится на то Многочлен не имеет кратных корней, так как он делит где мультипликативный порядок числа по модулю Следовательно, каждый неприводимый делитель многочлена имеет кратность Отсюда заключаем, что если неприводимый многочлен имеет период то период многочлена равен где наименьшая степень числа такая, что

Предположим теперь, что где различные неприводимые многочлены.

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

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

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

Таким образом, задача определения периода многочлена сводится к задаче определения периодов каждого из его неприводимых множителей. Каков наилучший метод определения периода неприводимого многочлена Если степень равна то должно быть делителем числа так что первый шаг сводится к разложению где различные простые числа. Определив классы вычетов можно узнать, входит ли в период число Эти вычисления могут быть выполнены путем перемножения подходящих комбинаций классов вычетов Если то период кратен числу если же то число не входит в период . В последнем случае надо проверить, кратен ли период числам Эти выкладки надо провести для всех простых делителей числа

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

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

Решение. Найдем матрицу строками которой являются четные степени редуцированные по модулю Это дает

Так как нуль-подпространство матрицы состоит из 1, то степень неприводимого многочлена. Так как многочлен не имеет общих делителей с то неприводимый многочлен. Затем находим классы вычетов каждый из которых получается с помощью умножения предыдущего класса на матрицу

Теперь надо определить, выполняется ли сравнение для некоторого собственного делителя числа Число не удовлетворяет этому условию, поскольку мы уже видели, что Проверим класс . В двоичной записи так что мы подсчитаем как произведение Это дает

Следовательно, период многочлена равен 73. Для средних значений наиболее трудоемкой частью вычисления периода неприводимого многочлена степени является разложение числа

Хотя в случае надобности можно получить такое разложение непосредственно, лучше пользоваться литературой, содержащей сводные результаты по этому вопросу, основанные на многих тонких исследованиях в сочетании со значительными вычислениями. Сопоставляя результаты отчета Брилхарта и Селфриджа [1967] с цитированными ими работами, можно получить таблицу полного разложения чисел для всех и для многих больших значений

Период многочлена и периоды его неприводимых делителей связаны с периодом многочлена Для того чтобы выяснить эту связь в общем случае, достаточно рассмотреть лишь некоторые случаи. Во-первых, можно предположить, что многочлен неприводим, так как если то и можно отдельно рассматривать Далее можно предположить, что простое, так как если то и анализ можно проводить в два этапа. Можно также исключить и тривиальный случай, когда равно характеристике поля. Остальные случаи описываются следующей теоремой:

6.23. Теорема. Пусть неприводимый многочлен степени над полем с периодом и пусть простое число, не делящее Если то период каждого неприводимого делителя многочлена равен Если то период одного неприводимого делителя многочлена равен а периоды остальных делителей равны

Доказательство. Согласно свойствам круговых многочленов, доказанным в разд. 4.3, . Если то и это доказывает первое утверждение. Если то где — минимальный многочлен для степеней корней многочлена Каждый многочлен неприводим, и делит тогда и только тогда, когда