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

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

. Таким образом получен алгоритм, известный под названием 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 достаточно велико, то алгоритм имеет огромную трудоёмкость,

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

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

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

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