Корни многочленов над конечными полями. Построение многочленов на основе заданных корней

 

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

,

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

Ранее (см. 8.1) полиномы трактовались как форма представления элементов расширенного поля, в которой формальная переменная служила указателем позиции соответствующего коэффициента. Рассмотрим теперь полиномы как обычные функции, допускающие подстановку вместо переменной некоторых значений. В частности, рассмотрим двоичные полиномы (т.е. полиномы над полем ) и подставим в них вместо переменной элементы некоторого расширенного поля. Если при подстановке в двоичный полином в качестве аргумента некоторого имеет место , то говорят, что элемент , лежащий в расширенном поле , является корнем полинома .

Пример 8.4.1. Рассмотрим полином . Путем простой подстановки элементов легко убедиться, что данный полином не имеет корней в основном поле: . Вместе с тем, обратившись к таблице 8.2 примера 8.2.5, можно увидеть, что , следовательно, является корнем полинома в поле .

Следующее утверждение, сформулированное в виде теоремы, демонстрирует параллель с обычной алгеброй, о которой уже упоминалось ранее.

Теорема 8.4.1. Если является корнем многочлена над полем , то и все сопряженные с ним по степени два элементы , также являются корнями полинома .

Доказательство: Пусть – корень полинома . Тогда при подстановке в выполняется соотношение

.

Если теперь в вместо подставить , то получим выражение

,

которое, с учетом теорем 8.3.1–8.3.2, преобразуется к виду

.

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

Пример 8.4.2. Возвращаясь к условиям примера 8.4.1, можно убедиться, что полином наряду с имеет корнями следующие элементы:

– ;

– ,

которые являются сопряженными по степени 2 с . Поскольку , то, следовательно, найдены все корни полинома .

Пусть – расширение простого поля и пусть – некоторый ненулевой элемент поля . Тогда приведенный неприводимый (или простой) полином наименьшей степени над , для которого , называется минимальным многочленом над . Обозначим подобный полином, как и сформулируем следующее утверждение.

Теорема 8.4.2. Пусть длина цикла сопряженных с по степени 2 элементов. Тогда

.

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

,

где – длина множества 2–сопряженных с элементов.

Пример 8.4.3. Используя результаты примера 8.4.2, решим обратную задачу построения минимального полинома для элемента . Тогда на основании последнего утверждения

.

что и следовало ожидать.

Теорема 8.4.3. В конечном поле , , любой ненулевой элемент удовлетворяет соотношению

или ,

а, значит, является корнем бинома

.

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

,

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

Тогда на основании теоремы 8.4.3 и того факта, что все ненулевые элементы поля могут быть выражены как некоторая степень примитивного элемента , выполняется соотношение