Факторизация полиномов над конечными полями

Министерство образования Российской Федерации

Ярославский государственный университет имени П.Г. Демидова

Математический факультет

Курсовая работа

на тему:

Факторизация полиномов над конечными полями (Алгоритм Берлекампа)

Выполнил: Степанов А.Ю.

Группа КБ-21

Ярославль, 2004

Краткий план.

1. Введение в алгебру полиномов.

2. Наибольшие общие делители полиномов над полем.

3. Неприводимые сомножители полиномов.

4. Разложение полиномов на свободные от квадратов множители.

5. Основные факты о конечных полях.

6. Разложение полиномов на множители в конечных полях.

7. Вычисление числа неприводимых полиномов над конечным полем.

8. Подход к алгоритму Берлекампа.

9. Алгоритм Берлекампа.

10. Пример.

1. Введение в алгебру полиномов. Пусть K – область целостности, x – независимая переменная – её можно рассматривать как просто формальный символ, а не как независимый аргумент области К. Тогда выражение вида

, где для

называется полиномом от переменной х над K.

Полиномы называются равными, если у них равны коэффициенты при соответствующих степенях х

Определим так сумму и произведение полиномов:

Очевидно, что сумма и произведение полиномов от х над К также представляют собой полином над K. Mножество полиномов от х над областью целостности К само является областью целостности, которая обозначается как K[x]. Покажем это. Возьмём полиномы и . Тогда их произведение . Знаком 0 здесь обозначен нулевой многочлен - . Предположим и , так что и не обращаются в 0. Следствием из этого является так как и являются элементами области целостности К. Но - коэффициент при старшем члене полинома-произведения, т.е. , что означает отсутствие в K[x] делителей нуля.

Рассмотрим полином - не равный тождественно 0 полином над К. Тогда полином делит полином если - некоторый полином над К, что . В этом случае используется запись . Полином называется делителем полинома .

Докажем важный факт, известный как свойство евклидовости:

Пусть К – область целостности, а и - два полинома над К[x] и пусть обратим в К. Тогда существуют единственные полиномы и (частное и остаток соответственно), что

, .

Доказательство производится индукцией по степени делимого .Если или то положим и . В противном случае пусть , и образуем полином . При этом так как убрана старшая степень х. В случае или - всё доказано. В противном случае по индукции для некоторых и , таких что . Поэтому , что и доказывает существование полиномов и . Ясно, что и - полиномы в кольце К[x], при этом либо либо . Для доказательства единственности предположим наличие другой пары и , такой что , . Тогда и . A это может иметь место только в случае . Следовательно и

Следует заметить, что если К – поле, то для наличия свойства евклидовости достаточно чтобы полином-делитель не был нулевым полиномом.

Легко можно составить алгоритм полиномиалного деления над полем, который более известен как алгоритм PDF (Polynomial Difvision over the Field).

Вход: и - два полинома, , причём

(кстати, алгоритм будет работать и над областью целостности, если в ней обратим)

Выход: и , обладающие свойством евкидовости.

Cам алгоритм будет состоять из двух частей:

1. FOR k=m-n DOWNTO 0 // основной вычислительный цикл

BEGIN

FOR j=n+k-1 DOWNTO k

BEGIN

END

END

2. FOR i=0 TO m-n // выдача результатов

BEGIN

RETURN

RETURN

END

Очевидно что доминирует первый цикл, который выполняется m-n+1 раз. В каждом цикле происходит одно деление и пересчитывается ряд коэффициентов. Таким образом трудоёмкость алгоритма PDF есть O[n(m-n+1)]. Это как раз то время, которое нужно для вычисления произведения над полем.

Наибольшие общие делители полиномов над полем. Дадим следующее

Определение. Пусть К – область целостности и , причём .

Полином называется Наибольшим Общим Делителем (НОД) полиномов и если выполнены следующие условия:

1. и

2. Если ,такой что и ,то и .

Отсюда виден так называемый алгоритм Евклида для нахождения НОД двух полиномов, также использующий теорему делимости, который работает следующим образом:

, при этом

. . .

. . .

, при этом

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

Теорема. Последний отличный от нуля остаток это и есть НОД( ).

Cледует учесть что НОД может быть определён не однозначно если в области целостности имеются обратимые элементы.

Теперь пусть имеется некоторое поле F, , . Применяя PDF можно вычислить НОД( ).

Пусть и - некоторые произвольные полиномы из . Тогда справедлива

Теорема. Если НОД( ), то в найдутся полиномы и , такие что

Доказательство: Из всех полиномов вида выберем любой из полиномов наименьшей степени и обозначим его . Если не делит , то , , . Но тогда полином имеет вид , в противоречие с выбором .

Из теоремы следует, что для взаимной простоты полиномов и необходимо и достаточно чтобы для некоторых .

Неприводимые сомножители полиномов. Для начала нужно сформулировать ряд известных теорем:

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

2. Отличный от константы полином из R[x] неприводим если и только если он имеет степень 1 либо это квадратный трёхчлен с отрицательным дискриминантом.

Имеет место обратное утверждение.

Теперь для полиномов над полем K – поле.

3.Если неприводимый полином делит произведение то или .

4. Пусть . Тогда полином может быть однозначно представлен в произведение неприводимых нормированных полиномов над K[x]. Разложение является единственным с точностью до порядка сомножителей.

Назовём полином примитивным, ecли его коэффициенты – целые числа, НОД которых равен 1. Тогда любой полином из ассоциирован с некоторым примитивным полиномом (два полинома называются ассоциированными, если один из них является скалярным кратным другого). Верна теорема

5. Произведение двух примитивных полиномов из снова примитивный полином.

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

, , откуда

Иначе говоря никакое простое число не делит все коэффициенты многочлена что и доказывает его примитивность.

6. (Gauss) Если , причём , то , где и - полиномы, ассоциированные с и соответственно.

Полином в неприводим если он не разлагается в произведение двух полиномов с целыми коэффициентами. В силу вышеприведённой теоремы видно, что полином неприводим в , если и только если он неприводим как полином из . При этом справедлива теорема

7. Если - полином в и - его корень, такой что НОД(r,s)=1, то и .

8. (критерий Эйзенштейна) Пусть - полином в . Если существует такое простое число p, что p не делит и делит остальные коэффициенты , но не делит , тогда полином неприводим.

Доказательство большинства из этих теорем опускается, иначе это уведёт от главной цели.

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

Теорема. Пусть K - область с однозначным разложением на множители, характеристики нуль. И пусть - примитивный полином в K[x], отличный от константы. Возьмём его однозначное разложение на множители . Его производную обозначим . Тогда НОД( , )=

Доказательство: Обозначим и r(x)= НОД( , ). Тогда и , откуда следует что . Методом от противного можно показать что не делит r(x). Предположим что . Тогда , откуда можно заключить что . Отсюда после сокращений . Cтало быть потому что НОД( )=1. Из этого можно заключить что . Очевидное противоречие.

Из теоремы легко выводятся два следствия.

Следствие1. Простые корни полинома не являются корнями его производной.

Cледствие2.