Министерство образования Российской Федерации
Ярославский государственный университет имени П.Г. Демидова
Математический факультет
на тему:
Факторизация полиномов над конечными полями (Алгоритм Берлекампа)
Выполнил: Степанов А.Ю.
Группа КБ-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 – взаимно простые. Тогда каждый делитель 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
)
Вход: Нормированный, свободный от квадратов полином
,
.
Выход: Неприводимые над
сомножители полинома
.
Описание реализации:
- Построить матрицу 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
– ранг матрицы М
.
Реализация:
- 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
достаточно велико, то алгоритм имеет огромную трудоёмкость, связанную с вычислением НОДов для всех
|