Реферат: Краткий план. Введение в алгебру полиномов. Наибольшие общие делители полиномов над полем

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

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

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

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

на тему:

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

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

Группа КБ-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 (P olynomial D ifvision 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 Sq uare F ree F actorization).

Вход: - примитивный полином, определённый на области с однозначным разложением на множители 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 разложения на свободные от квадратов множители над конечным полем (P olynomial Sq uare-free F actorization over a F inite F ield) :

Вход: - нормированный полином из , не являющийся константой, 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 – взаимно простые. Тогда каждый делитель в числа может быть представлен в виде произведения взаимно простых , таких что и . Поэтому

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

Если , то .

Доказательство: Функция является мультипликативной, если 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), соответствуя полиному . Вторая строка представляет , третья , четвёртая .

Пусть . Предположим, что . Тогда или

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

. Здесь , .

Эти формулы объясняют вычисление . Вычисления можно проводить используя массив . В цикле , ,…, , . Результаты отображаем в таблице:

Нетрудно видеть вторую строку матрицы 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 достаточно велико, то алгоритм имеет огромную трудоёмкость, связанную с вычислением НОДов для всех . Лучший способ вычислений был предложен Кантором и Пассенхаузом, и с ними мне предстоит разобраться в следующей курсовой работе.