11.6. Простые многочлены

Простой многочлен — это такой унитарный многочлен, который нельзя разложить на произведение двух многочленов более низкой степени. Однако, поскольку для коэффициентов рассматривается поле с арифметикой по модулю 2, то нужно разобраться какой вид приобретают обычные представления о многочленах Проведем экспериментальное исследование возникающих явлений. При этом опустим доказательство свойств конечных полей, которые необходимы для изучения разложения на множители.

В случае многочленов степени имеется один тривиальный многочлен (если этот вырожденный элемент заслуживает названия многочлена), а именно . В обычной арифметике ему соответствует число 1.

Имеется ровно два унитарных многочлена степени 1, а именно и оба они являются простыми (аналогично тому, что тривиальный множитель 1 не учитывается при разложении чисел на множители, при разложении многочленов не учитывается тривиальный многочлен 1).

Имеется четыре различных унитарных многочлена степени 2 (каждый коэффициент при и при 1 может быть или 1):

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

Уверены ли мы в том, что многочлен является простым? Попробуем разделить его на каждый из двух многочленов меньшей степени. Если бы многочлен был приводим, то соответствующими сомножителями могли бы быть только указанные два многочлена первой степени. Ясно, что не является делителем. Попробуем провести деление на

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

В качестве примера рассмотрим еще восемь возможных кубических многочленов:

Здесь приведены очевидные разложения на множители, а для остальных многочленов оставлены пробелы.

Если кубический многочлен можно разложить на множители, то один из сомножителей должен быть многочленом первой степени. Поскольку все многочлены, делящиеся на указаны в таблице, осталось рассмотреть сомножитель Для имеем

Поэтому

Возьмем теперь многочлен Имеем

Поэтому многочлен является простым. Аналогично, простым является многочлен поскольку

Наконец, рассмотрим многочлен Приведенные выше вычисления подсказывают, как разложить этот многочлен на множители, т. е. можно записать и многочлен не является простым.

Таким образом, простыми унитарными многочленами степени 3 будут только многочлены

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

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

Задачи

11.6.1. Докажите следующую теорему: сумма коэффициентов многочлена равна по модулю 2 в том и только том случае, когда многочлен делится на

11.6.2. Зная число многочленов данной степени и число различных произведений простых многочленов меньших степеней, получите число простых многочленов данной степени.