Главная » Каталог    
рефераты Разделы рефераты
рефераты
рефератыГлавная

рефератыБиология

рефератыБухгалтерский учет и аудит

рефератыВоенная кафедра

рефератыГеография

рефератыГеология

рефератыГрафология

рефератыДеньги и кредит

рефератыЕстествознание

рефератыЗоология

рефератыИнвестиции

рефератыИностранные языки

рефератыИскусство

рефератыИстория

рефератыКартография

рефератыКомпьютерные сети

рефератыКомпьютеры ЭВМ

рефератыКосметология

рефератыКультурология

рефератыЛитература

рефератыМаркетинг

рефератыМатематика

рефератыМашиностроение

рефератыМедицина

рефератыМенеджмент

рефератыМузыка

рефератыНаука и техника

рефератыПедагогика

рефератыПраво

рефератыПромышленность производство

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

рефератыРеклама

рефератыРефераты по геологии

рефератыМедицинские наукам

рефератыУправление

рефератыФизика

рефератыФилософия

рефератыФинансы

рефератыФотография

рефератыХимия

рефератыЭкономика

рефераты
рефераты Информация рефераты
рефераты
рефераты

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

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

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

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

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

на тему:

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

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

Группа КБ-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ледовательно,

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

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

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

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

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

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

. Таким образом получен алгоритм, известный под названием PSQFF(P

olynomial Square Free Factorization).

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

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

, char(K)=0.

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

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

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

На условном языке программирования алгоритм выглядит примерно так:

BEGIN // первоначальная инициализация

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

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

j:=1

label:

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

BEGIN

e:=j

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

EXIT

END

v(x):= Курсовая: Факторизация полиномов над конечными полями // вычисляем Курсовая: Факторизация полиномов над конечными полями

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

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

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

INCR(j)

GOTO label

END

Основные факты о конечных полях. Из определения поля видно, что каждое

поле – область целостности, обратное утверждение в общем случае неверно. Но

имеет место следующее утверждение:

Каждая конечная область целостности – поле.

Если взять два неравных элемента a,b из конечной области целостности K ,

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

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

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

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

означает наличие у каждого ненулевого элемента конечной области целостности

мультипликативного обратного элемента, что и подтверждает что K- поле.

Так как ненулевые элементы любого конечного поля из q элементов образуют

абелеву группу порядка q-1 относительно умножения, то справедлива

Теорема1. Если F - поле, |F|=q, Курсовая: Факторизация полиномов над конечными полями , Курсовая: Факторизация полиномов над конечными полями , то Курсовая: Факторизация полиномов над конечными полями .

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

Теорема2. Пусть F - поле, |F|=q, Курсовая: Факторизация полиномов над конечными полями , Курсовая: Факторизация полиномов над конечными полями . Если n – порядок элемента a, то n|(q-1).

Теорема3. Пусть F – поле, |F|=q, тогда Курсовая: Факторизация полиномов над конечными полями , p – простое, Курсовая: Факторизация полиномов над конечными полями .

Cледствие. Если F – конечное поле, то оно имеет характеристику p –

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

.

Теорема о примитивном корне (4). Элемент группы называется примитивным корнем,

если его степени 0,1,2,. пробегают все элементы группы. Cуть теоремы в том, что

в поле F из q элементов найдётся элемент а , что каждый ненулевой

элемент поля представляет степень а, т.е. a – примитивный

корень, и порядок элемента а равен q-1.

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

- нормализованный полином из F[х]. Тогда существует таккое содержащее F

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

разлагается в произведение линейных сомножителей. Это поле К называют полем

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

примеру,

C – поле расщепления для любого полинома из Q[x].

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

некоторого ненулевого полинома из F[x]. Тогда элемент х

называют алгебраичным над F. Иначе – трансцендентным.

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

алгебраичен над F. Тогда существует единственный неприводимый

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

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

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

а делится на m(x). Этот полином называют минимальным полиномом

элемента а над F.

Разложение полиномов на множители в конечных полях. Любой полином степени

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

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

возможных полиномов степени <n, но такой алгоритм "проб и ошибок” чрезмерно

трудоёмкий(этот алгоритм осуществляется через PDF). Так что неплохо бы иметь

более быстрые алгоритмы.

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

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

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

для каждого i. Это будет выполнено в случаях p|i или Курсовая: Факторизация полиномов над конечными полями

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

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

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

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

Теорема. Пусть K - область с однозначным разложением на множители, произвольной

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

- примитивный полином в K[x], отличный от константы. Возьмём его однозначное

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

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

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

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

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

Доказательство данной полностью аналогично доказательству уже доказанной

теоремы.

На этой теореме также основана некоторая модификация алгоритма PSQFF, но

перед этим нужно доказать ещё две вспомогательные теороемы.

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

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

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

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

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

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

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

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

в том и только в том случае, когда p(x) eсть р-ая степень некоторого полинома Курсовая: Факторизация полиномов над конечными полями

.

Доказательство:

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

Таким образом получен следующий алгоритм PSQFFF разложения на свободные от

квадратов множители над конечным полем (Polynomial Square-free

Factorization over a Finite Field) :

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

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

, не являющийся константой, p>0 – простое число.

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

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

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

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

Реализация:

BEGIN

k:=0; m:=1; e:=0 // инициализировали

label3:

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

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

label2:

e1:=j*m; IF e1>e THEN FOR i:=e to e1-2 do Курсовая: Факторизация полиномов над конечными полями ;

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

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

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

BEGIN

Курсовая: Факторизация полиномов над конечными полями ; Курсовая: Факторизация полиномов над конечными полями ; incr(j); GOTO label2

END

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

label1: Курсовая: Факторизация полиномов над конечными полями ; inkr(k); m:=m*p; GOTO label3;

END

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

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

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

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

, степени которых делят n. Отсюда степень произведения всех неприводимых

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

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

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

Введём для Курсовая: Факторизация полиномов над конечными полями функцию Мёбиуса Курсовая: Факторизация полиномов над конечными полями следующим образом:

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

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

если n раскладывается в произведение r различных простых чисел

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

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

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

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

мультипликативная функция. А для мультипликативных функций верна теорема

Если f – мультипликативная функция, а функция F определена

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

F – также мультипликативная функция.

Доказательство: Пусть числа m и n – взаимно простые. Тогда каждый делитель d

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

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

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

. Поэтому

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

Теперь ещё небольшой факт:

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

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

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

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

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

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

, из этого всего и следует это утверждение.

Формула обращения Мёбиуса. Для любой функции f, определённой на множестве

натуральных чисел (не обязательно мультипликативной), если

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

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

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

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

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

.

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

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

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

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

.

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

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

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

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

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

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

Причём если полином приводим то тест сработает достаточно быстро. Для

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

. Для исправления этого создан

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

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

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

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

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

делители n.

Алгоритм Берлекампа разложения на множители над конечными полями. Идея

Берлекампа основана на китайской теореме об остатках для полиномов:

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

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

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

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

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

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

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

. Это же можно сформулировать на языке отображений:

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

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

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

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

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

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

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

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

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

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

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

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

Теорема. В поле GF(p) – поле Галуа (конечное поле, содержащее p (простое

число) элементов) имеет место разложение:

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

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

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

, то есть (x-s) является делителем Курсовая: Факторизация полиномов над конечными полями

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

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

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

это два нормированных полинома, из этого всего и следует их равенство.

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

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

Теорема. Пусть Курсовая: Факторизация полиномов над конечными полями и Курсовая: Факторизация полиномов над конечными полями - два нормированных полинома над GF(p), такие что

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

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

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

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

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

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

- свободный от квадратов полином степени n, который нужно разложить на множители

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

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

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

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

корней. А именно 0,1.p-1. Значит он раскладывается следующим образом Курсовая: Факторизация полиномов над конечными полями

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

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

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

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

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

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

- нетривиальное разложение полинома над GF(p).

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

. Это можно осуществить с помощью решения систем линейных уравнений, получаемой

следующим образом. Пусть

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

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

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

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

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

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

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

на соответствующие выражения, получим

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

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

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

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

. Поэтому полином степени n будет делить этот полином если только он равен нулю.

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

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

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

.

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

коэффициенты полиномов остатков. По этому всему имеет место

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

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

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

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

. У этого пространства имеется базис и размерность.

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

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

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

.

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

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

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

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

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

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

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

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

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

. Для вопроса о неприводимости получен

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

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

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

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

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

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

- степень неприводимого полинома. Тогда берём r(x)=1.

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

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

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

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

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

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

.

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

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

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

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

.

Алгоритм BA (Berlecamp’s Algorithm)

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

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

Описание реализации:

  1. Построить матрицу Q.

2. Триангуляция этой матрицы. Привести матрицу Q к треугольному виду,

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

). Здесь r – число неприводимых сомножителей полинома. Так как решением

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

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

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

. И если r=1 то полином неприводим и алгороитм завершает работу.

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

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

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

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

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

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

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

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

найденных к данному времени, k=3,4,.,r, пока не найдётся r сомножителей. Это

гарантируется предидущими теоремами.

На шаге 2 этого алгоритма матрица матрица Q приводится к треугольному виду,

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

. Так как требуется не более p вычислений НОД для каждого базисного вектора и не

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

. Так что алгоритм не очень эффективен при больших p. Разберём

Пример. Разложим над GF(13) полином Курсовая: Факторизация полиномов над конечными полями , свободный от квадратов.

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

.

Для начала вычислим обратные элементы ненулевым элементам GF(13) (1,.,12).

Это соответственно будут (1,7,9,10,8,11,2,5,3,4,6,12).

Первая строка матрицы Q [4x4] всегда представляет собой (1,0,0,0), соответствуя

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

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

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

.

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

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

. Что означает

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

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

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

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

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

. Результаты отображаем в таблице:

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

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

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

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

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

00001
10010
20100
31000
4912115
52206
6711210
79899
811046
98693
100201
112010
12512910
1354012

Нетрудно видеть вторую строку матрицы Q: (12,0,4,5). Аналогично строим для

k=26,39 и получаем матрицу

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

Теперь нужно находить нуль-пространство матрицы Q-I. На основании

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

(Null-Space algorithm):

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

Выход: Линейно независимые вектора Курсовая: Факторизация полиномов над конечными полями , такие что Курсовая: Факторизация полиномов над конечными полями , n-r – ранг матрицы М.

Реализация:

  1. r:=0; Курсовая: Факторизация полиномов над конечными полями ,., Курсовая: Факторизация полиномов над конечными полями

2. Для h от 0 до n-1 : если найдётся столбец с номером h и Курсовая: Факторизация полиномов над конечными полями

, Курсовая: Факторизация полиномов над конечными полями , j=0,.,n-1, то

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

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

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

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

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

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

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

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

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

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

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

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

в противном случае.

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

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

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

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

для i=1,2,3 – выбор на данном этапе полностью произволен, хотя он и влияет на

получаемые при выходе векторы. Берём j=0 и после ранее описанных преобразований

матрица Q имеет вид:

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

Второй элемент в первом столбце 12 – означает Курсовая: Факторизация полиномов над конечными полями . Для h=2 матрица будет

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

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

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

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

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

.

Из вида матрицы Q-I при h=3 видно, что векторы Курсовая: Факторизация полиномов над конечными полями

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

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

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

должен иметь только два неприводимых сомножителя над GF(13).

Теперь нужно переходить к третьему шагу алгоритма Берлекампа, в котором

непосредственно найдутся эти сомножители. Этот шаг состоит в нахождении Курсовая: Факторизация полиномов над конечными полями

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

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

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

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

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

Но если p достаточно велико, то алгоритм имеет огромную трудоёмкость,

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

. Лучший способ вычислений был предложен Кантором и Пассенхаузом, и с ними мне

предстоит разобраться в следующей курсовой работе.

рефераты Рекомендуем рефератырефераты

     
Рефераты @2011