4.7. Определение минимальных многочленов

Если корень в неприводимого многочлена степени над то каждый элемент поля может быть представлен в виде многочлена от степени Каждый элемент из является корнем некоторого минимального многочлена над степень которого делит Часто бывает необходимо определить этот минимальный многочлен.

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

Наиболее простое решение этой задачи состоит в представлении элементов в виде многочленов от и нахождении их линейной комбинации, равной 0. Для настоящего примера имеем

Решая уравнение

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

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

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

В поле характеристики эти вычисления упрощаются, если для биномиальных коэффициентов известны сравнения по модулю Эти сравнения впервые были исследованы Лукасом в 1878 г.

4.71. Теорема Лукаса. Если простое и

то

Доказательство. Согласно теореме 4.404,

Продолжая вычисления, получаем

Сравним коэффициенты при

Полагая при получим, что

для любых

На основании этого факта доказательство теоремы легко завершается прямым применением индукции по

Замечание. Теорема не верна для непростых Например,

4.72. Следствие. за исключением того случая, когда для всех

4.73. Пример. Предположим, что элемент из с минимальным многочленом Каков минимальный многочлен элемента

Ответ. Работая по модулю два, получаем:

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

обращения (выписывания в обратном порядке) коэффициентов

Существуют также методы, позволяющие определить по для других значений к. Такие методы были описаны Дэйкином [1965], Голомбом [1967] и другими. В качестве примера таких методов рассмотрим определение в поле характеристики 2 по заданному Так как корни являются кубами корней то должен делить Аналогично, если примитивный кубический корень из единицы , то также должны делить . С другой стороны, каждый корень многочлена является корнем либо либо либо Следовательно,

4.74. Теорема. Многочлен является степенью многочлена

Зная можно вычислить Так как то многочлен может быть представлен в виде квадратного многочлена от коэффициентами которого являются многочлены от х.

где

Например, пусть необходимо определить при Тогда Следуя Голомбу [1967], вычисления будем производить с помощью таблицы 4.2, выписывая только показатели степеней ненулевых членов

Таблица 4.2

Кубическое преобразование многочлена

многочлена. Начнем с записи в столбце А показателей членов многочлена которые в столбце В — показателей, которые в столбце С — показателей, которые Затем найдем члены вида (смешанные) в выражении . В общем случае и

Смешанные члены имеют вид так как при . В рассматриваемом примере смешанные члены дают: Деля эти кубические смешанные члены на 3, мы получаем 4 и 2, приведенные в таблице. Аналогично мы подсчитываем кубические смешанные члены для Это Деля эти кубические смешанные члены на 3, получаем 3 и 2, приведенные в таблице. Наконец, найдем члены произведения . В данном примере таких членов четыре: Их деление на 3 дает числа 1, 2, 3 и 4, приведенные в таблице. Произведя суммирование по столбцам и учитывая подобные члены, получаем 0, 4, 6. Значит, так что степень многочлена Так как неприводим, то

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

Таблица 4.3 (см. скан) Кубическое преобразование многочленов

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

В качестве последнего примера вычислим минимальные многочлены всех элементов поля если . В таблице 4.3 выписаны результаты вычисления Повторяя преобразование, вычисляем затем Зная тривиальным образом вычисляем Это дает все неприводимые двоичные многочлены пятой степени, приведенные в таблице 4.4.

Таблица 4.4 (см. скан) Минимальные многочлены элементов поля

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

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

Задачи

(см. скан)

(см. скан)

(см. скан)