РУБРИКИ

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

 РЕКОМЕНДУЕМ

Главная

Правоохранительные органы

Предпринимательство

Психология

Радиоэлектроника

Режущий инструмент

Коммуникации и связь

Косметология

Криминалистика

Криминология

Криптология

Информатика

Искусство и культура

Масс-медиа и реклама

Математика

Медицина

Религия и мифология

ПОДПИСКА НА ОБНОВЛЕНИЕ

Рассылка рефератов

ПОИСК

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

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

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

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

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

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

на тему:

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

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

Группа КБ-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 F

ield).

Вход: Курсовая: Факторизация полиномов над конечными полями и Курсовая: Факторизация полиномов над конечными полями - два полинома, Курсовая: Факторизация полиномов над конечными полями , причём Курсовая: Факторизация полиномов над конечными полями

(кстати, алгоритм будет работать и над областью целостности, если в ней Курсовая: Факторизация полиномов над конечными полями

обратим)

Выход: Курсовая: Факторизация полиномов над конечными полями и Курсовая: Факторизация полиномов над конечными полями , обладающие свойством евкидовости.

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. Пусть K – поле, Курсовая: Факторизация полиномов над конечными полями

- неприводимый полином в K[x], который делит Курсовая: Факторизация полиномов над конечными полями

. Тогда Курсовая: Факторизация полиномов над конечными полями если и

только если Курсовая: Факторизация полиномов над конечными полями .

Пусть Курсовая: Факторизация полиномов над конечными полями - примитивный

полином, определённый на области с однозначным разложением на множители K, Курсовая: Факторизация полиномов над конечными полями

. Пусть Курсовая: Факторизация полиномов над конечными полями . Для Курсовая: Факторизация полиномов над конечными полями

положим Курсовая: Факторизация полиномов над конечными полями , Курсовая: Факторизация полиномов над конечными полями

. Тогда Курсовая: Факторизация полиномов над конечными полями называется

разложением полинома Курсовая: Факторизация полиномов над конечными полями

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

Замечание. Некоторые из полиномов Курсовая: Факторизация полиномов над конечными полями

могут быть единицей, Курсовая: Факторизация полиномов над конечными полями

- произведение всех линейных множителей, cоответствующим простым корням, Курсовая: Факторизация полиномов над конечными полями

- произведение всех линейных множителей, cоответствующим двойным корням и т.д.

Так как r(x)= НОД(Курсовая: Факторизация полиномов над конечными полями ,Курсовая: Факторизация полиномов над конечными полями )=Курсовая: Факторизация полиномов над конечными полями (здесь без Курсовая: Факторизация полиномов над конечными полями ).

Наибольший свободный от квадратов делитель полинома Курсовая: Факторизация полиномов над конечными полями равен Курсовая: Факторизация полиномов над конечными полями .

Cледовательно,

НОД(Курсовая: Факторизация полиномов над конечными полями ,Курсовая: Факторизация полиномов над конечными полями )=Курсовая: Факторизация полиномов над конечными полями .

Поэтому Курсовая: Факторизация полиномов над конечными полями . Повторяя

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

мы можем вычислить Курсовая: Факторизация полиномов над конечными полями

как первый свободный от квадратов сомножитель Курсовая: Факторизация полиномов над конечными полями

, и в конце можно получить все свободные от квадратов сомножители Курсовая: Факторизация полиномов над конечными полями

Страницы: 1, 2


© 2010
Частичное или полное использование материалов
запрещено.