Если
где
не делится на
то
Многочлен
не имеет кратных корней, так как он делит
где
мультипликативный порядок числа
по модулю
Следовательно, каждый неприводимый делитель многочлена
имеет кратность
Отсюда заключаем, что если неприводимый многочлен
имеет период
то период многочлена
равен
где
наименьшая степень числа
такая, что
Предположим теперь, что
где
различные неприводимые многочлены.
Так как
делит
тогда и только тогда, когда к делит
то период
равен наименьшему общему кратному периодов многочленов
Это число в свою очередь равно произведению наименьшего общего кратного периодов многочленов
на наименьшую степень
числа
такую, что
для всех
Итак, имеет место
6.21. Теорема. Если
где
неприводимые многочлены с периодами
над полем
характеристики
то период
равен произведению наименьшего общего кратного чисел
на такую наименьшую степень
числа
что
для всех
Таким образом, задача определения периода многочлена сводится к задаче определения периодов каждого из его неприводимых множителей. Каков наилучший метод определения периода
неприводимого многочлена
Если степень
равна
то
должно быть делителем числа
так что первый шаг сводится к разложению
где
различные простые числа. Определив классы вычетов
можно узнать, входит ли в период
число
Эти вычисления могут быть выполнены путем перемножения подходящих комбинаций классов вычетов
Если
то период
кратен числу
если же
то число
не входит в период
. В последнем случае надо проверить, кратен ли период
числам
Эти выкладки надо провести для всех простых делителей числа
Результаты этих вычислений сразу позволяют определить период
многочленов
6.22. Пример. Чему равна блоковая длина укороченного циклического двоичного кода с порождающим многочленом
Хотя в случае надобности можно получить такое разложение непосредственно, лучше пользоваться литературой, содержащей сводные результаты по этому вопросу, основанные на многих тонких исследованиях в сочетании со значительными вычислениями. Сопоставляя результаты отчета Брилхарта и Селфриджа [1967] с цитированными ими работами, можно получить таблицу полного разложения чисел
для всех
и для многих больших значений
Период многочлена
и периоды его неприводимых делителей связаны с периодом многочлена
Для того чтобы выяснить эту связь в общем случае, достаточно рассмотреть лишь некоторые случаи. Во-первых, можно предположить, что многочлен
неприводим, так как если
то
и можно отдельно рассматривать
Далее можно предположить, что
простое, так как если
то
и анализ можно проводить в два этапа. Можно также исключить и тривиальный случай, когда
равно характеристике поля. Остальные случаи описываются следующей теоремой:
6.23. Теорема. Пусть
неприводимый многочлен степени
над полем
с периодом
и пусть
простое число, не делящее
Если
то период каждого неприводимого делителя многочлена
равен
Если
то период одного неприводимого делителя многочлена
равен
а периоды остальных делителей равны
Доказательство. Согласно свойствам круговых многочленов, доказанным в разд. 4.3,
. Если
то
и это доказывает первое утверждение. Если
то
где
— минимальный многочлен для
степеней корней многочлена
Каждый многочлен
неприводим, и
делит
тогда и только тогда, когда