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