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

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

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

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

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

Ярославль, 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), соответствуя

полиному . Вторая

строка представляет

, третья , четвёртая

.

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

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

. Здесь , .

Эти формулы объясняют вычисление

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

. В цикле ,

,., ,

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

0	0	0	0	1
1	0	0	1	0
2	0	1	0	0
3	1	0	0	0
4	9	12	11	5
5	2	2	0	6
6	7	11	2	10
7	9	8	9	9
8	11	0	4	6
9	8	6	9	3
10	0	2	0	1
11	2	0	1	0
12	5	12	9	10
13	5	4	0	12

Нетрудно видеть вторую строку матрицы 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 достаточно велико, то алгоритм имеет огромную трудоёмкость,

связанную с вычислением НОДов для всех

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

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