В математике и компьютерной алгебры разложение многочлена состоит из разложения его в продукт из неприводимых множителей . Это разложение теоретически возможно и является уникальным для многочленов с коэффициентами в любом поле , но необходимы довольно строгие ограничения на поле коэффициентов, чтобы можно было вычислить факторизацию с помощью алгоритма . На практике алгоритмы разрабатывались только для многочленов с коэффициентами в конечном поле , в области рациональных чисел или вконечно порожденное расширение поля одного из них.
Все алгоритмы факторизации, включая случай многомерных многочленов над рациональными числами, сводят проблему к этому случаю; см. полиномиальную факторизацию . Он также используется для различных приложений конечных областей, таких как теория кодирования ( циклические избыточные коды и коды BCH ), криптография ( криптография с открытым ключом с помощью эллиптических кривых ) и вычислительная теория чисел .
Поскольку сведение факторизации многомерных многочленов к факторизации одномерных многочленов не имеет какой-либо специфики в случае коэффициентов в конечном поле, в данной статье рассматриваются только многочлены с одной переменной.
Задний план
Конечное поле
Теория конечных полей, истоки которой восходят к работам Гаусса и Галуа , сыграла свою роль в различных разделах математики. Из-за применимости концепции к другим темам математики и наук, таким как информатика, возродился интерес к конечным областям, и это частично связано с важными приложениями в теории кодирования и криптографии . Приложения конечных полей представляют некоторые из этих достижений в криптографии , компьютерной алгебре и теории кодирования .
Конечное поле или поле Галуа - это поле с конечным порядком (числом элементов). Порядок конечного поля - всегда простое число или степень простого числа. Для каждой степени простого q = p r существует ровно одно конечное поле из q элементов с точностью до изоморфизма. Это поле обозначается GF ( q ) или F q . Если p простое, GF ( p ) простое поле порядка p ; это поле классов вычетов по модулю p , и его p элементов обозначаются 0, 1, ..., p −1. Таким образом, a = b в GF ( p ) означает то же самое, что и a ≡ b (mod p ).
Неприводимые полиномы
Пусть F - конечное поле. Что касается общих полей, непостоянный многочлен f в F [ x ] называется неприводимым над F, если он не является произведением двух многочленов положительной степени. Полином положительной степени , что не является неприводимым над F называется приводимым над F .
Неприводимые полиномы позволяют строить конечные поля непростого порядка. Фактически, для степени q простого числа пусть F q - конечное поле с q элементами, единственное с точностью до изоморфизма. Полином f степени n больше единицы, неприводимый над F q , определяет расширение поля степени n, которое изоморфно полю с q n элементами: элементы этого расширения - многочлены степени ниже n ; сложение, вычитание и умножение на элемент F q являются таковыми для многочленов; произведение двух элементов - это остаток от деления их произведения в виде полиномов на f ; Обратный элемент может быть вычислен с помощью расширенного алгоритма GCD (см. Арифметика алгебраических расширений ).
Отсюда следует, что для вычисления в конечном поле непростого порядка необходимо сгенерировать неприводимый многочлен. Для этого обычно используют случайный многочлен и проверяют его на неприводимость. Для эффективности умножения в поле обычно ищут многочлены вида x n + ax + b . [ необходима цитата ]
Неприводимые полиномы над конечными полями также полезны для генераторов псевдослучайных чисел, использующих регистры сдвига с обратной связью и дискретный логарифм над F 2 n .
Число неприводимых монических многочленов степени n над F q - это количество апериодических ожерелий , заданное функцией подсчета ожерелий Моро M q ( n ). Тесно связанная функция ожерелья N q ( n ) подсчитывает монические многочлены степени n, которые являются примарными (степень неприводимого); или же неприводимые многочлены всех степеней d, которые делят n. [1]
Пример
Многочлен P = x 4 + 1 неприводим над Q, но не над любым конечным полем.
- На любое расширение поля F 2 , P = ( х + 1) 4 .
- На любом другом конечном поле по крайней мере одно из значений −1, 2 и −2 является квадратом, потому что произведение двух неквадратов является квадратом, и поэтому мы имеем
- Если тогда
- Если тогда
- Если тогда
Сложность
Алгоритмы полиномиального разложения используют основные полиномиальные операции, такие как произведения, деления, НОД, степени одного полинома по модулю другого и т. Д. Умножение двух полиномов степени не выше n может быть выполнено за O ( n 2 ) операций в F q с использованием «классического "арифметические операции , или за O ( n log ( n ) log (log ( n ))) операций в F q с использованием " быстрой "арифметики . Евклидово деление (деление с остатком) могут быть выполнены в пределах одних и тех же временных границ. Стоимость полиномиального наибольшего общего делителя между двумя полиномами степени не выше n может быть взята как O ( n 2 ) операций в F q с использованием классических методов или как O ( n log 2 ( n ) log (log ( n )) ) операций в F q быстрыми методами. Для полиномов h , g степени не выше n возведение в степень h q mod g может быть выполнено с помощью полиномиальных произведений O (log ( q )), используя возведение в степень методом возведения в квадрат , то есть O ( n 2 log ( q )) операций в F q с использованием классических методов или O ( n log ( q ) log ( n ) log (log ( n ))) операций в F q с использованием быстрых методов.
В следующих алгоритмах сложности выражаются в количестве арифметических операций над F q с использованием классических алгоритмов арифметики многочленов.
Алгоритмы факторинга
Многие алгоритмы факторизации многочленов по конечным полям включают следующие три этапа:
- Факторизация без квадратов
- Факторизация с четкой степенью
- Факторизация с равной степенью
Важным исключением является алгоритм Берлекампа , который объединяет этапы 2 и 3.
Алгоритм Берлекампа
Алгоритм Берлекампа исторически важен как первый алгоритм факторизации, который хорошо работает на практике. Однако он содержит петлю на элементах основного поля, что означает, что это возможно только для небольших конечных полей. Для фиксированного основного поля его временная сложность полиномиальна, но для общих основных полей сложность экспоненциально зависит от размера основного поля.
Факторизация без квадратов
Алгоритм определяет факторизацию без квадратов для многочленов, коэффициенты которых берутся из конечного поля F q порядка q = p m с простым p . Этот алгоритм сначала определяет производную, а затем вычисляет НОД полинома и его производную. Если это не один, то НОД снова делится на исходный многочлен при условии, что производная не равна нулю (случай, который существует для непостоянных многочленов, определенных над конечными полями).
В этом алгоритме используется тот факт, что если производная многочлена равна нулю, то это многочлен от x p , который, если коэффициенты принадлежат F p , является p- й степенью многочлена, полученного заменой x на x 1. / стр . Если коэффициенты не принадлежат F p , корень p -й степени многочлена с нулевой производной получается той же подстановкой на x , завершенной применением к коэффициентам обратного автоморфизма Фробениуса . [ необходима цитата ]
Этот алгоритм работает также над полем нулевой характеристики с той лишь разницей, что он никогда не входит в блоки инструкций, где вычисляются корни p- й степени. Однако в этом случае алгоритм Юна намного эффективнее, потому что он вычисляет наибольшие общие делители многочленов более низких степеней. Следствием этого является то, что при факторизации многочлена по целым числам следующий алгоритм не используется: сначала вычисляется факторизация без квадратов по целым числам, а для факторизации полученных многочленов выбирается p так , чтобы они оставались квадратичными. свободный по модулю p .
Алгоритм : SFF (факторизация без квадратов) Вход : монический многочлен f в F q [ x ], где q = p m Выход : факторизация без квадратов f R ← 1 # Сделать w произведением (без кратности) всех множителей f, которые имеют # кратность, не делящаяся на p c ← gcd ( f , f ′) w ← f / c # Шаг 1. Определите все множители в w i ← 1, в то время как w g 1 do y ← gcd ( w , c ) fac ← w / y R ← R · fac i w ← y ; c ← c / y ; i ← i + 1 end, в то время как # c теперь является произведением (с кратностью) оставшихся множителей f # Шаг 2. Определите все оставшиеся факторы с помощью рекурсии # Обратите внимание, что это множители f , кратность которых делится на p, если c ≠ 1, то c ← c 1 / p R ← R · SFF ( c ) p end, если Выход ( R )
Идея состоит в том, чтобы идентифицировать произведение всех неприводимых множителей f с одинаковой кратностью. Это делается в два этапа. На первом этапе используется формальная производная от f, чтобы найти все множители с кратностью, не делящейся на p . На втором этапе определяются оставшиеся факторы. Поскольку все остальные множители имеют кратность, кратную p , что означает, что они являются степенями p , можно просто взять квадратный корень p -й степени и применить рекурсию.
Пример бесквадратной факторизации
Позволять
должны быть разложены по полю с тремя элементами.
Алгоритм сначала вычисляет
Поскольку производная не равна нулю, мы имеем w = f / c = x 2 + 2, и мы входим в цикл while. После одного цикла у нас есть y = x + 2 , z = x + 1 и R = x + 1 с обновлениями i = 2 , w = x + 2 и c = x 8 + x 7 + x 6 + x 2 + x + 1 . При втором прохождении цикла получается y = x + 2 , z = 1 , R = x + 1 , с обновлениями i = 3 , w = x + 2 и c = x 7 + 2 x 6 + x + 2 . Третий раз через петлю , также не изменяется R . В четвертый раз в цикле мы получаем y = 1 , z = x + 2 , R = ( x + 1) ( x + 2) 4 , с обновлениями i = 5 , w = 1 и c = x 6 + 1 . Поскольку w = 1, мы выходим из цикла while. Поскольку c ≠ 1, это должен быть идеальный куб. Кубический корень из c , полученный заменой x 3 на x, равен x 2 + 1, и вызов процедуры без квадратов рекурсивно определяет, что он не содержит квадратов. Следовательно, его кубирование и объединение со значением R до этой точки дает разложение без квадратов
Факторизация с четкой степенью
Этот алгоритм разбивает многочлен без квадратов на произведение многочленов, все неприводимые множители которых имеют одинаковую степень. Пусть f ∈ F q [ x ] степени n - факторизуемый многочлен.
Алгоритм Факторизация с разной степенью (DDF) Вход : монический многочлен без квадратов f ∈ F q [ x ] Выход : множество всех пар ( g , d ) , таких, что f имеет неприводимый множитель степени d, а g является произведение всех монических неприводимых сомножителей f степени d . Начинать пока делать если g ≠ 1 , то ; конец, если i : = i + 1; конец пока ; если , то ; если , затем верните {( f , 1)} , иначе верните S End
Правильность алгоритма основана на следующем:
Лемма. При i ≥ 1 многочлен
является произведением всех монических неприводимых многочленов из F q [ x ], степень которых делит i .
На первый взгляд, это неэффективно, поскольку требует вычисления НОД полиномов степени, экспоненциальной от степени входного полинома. тем не мение
может быть заменен на
Следовательно, мы должны вычислить:
есть два метода:
Метод I. Начнем со значения
вычисленный на предыдущем шаге, и вычислить его q-ю степень по модулю нового f * , используя возведение в степень методом возведения в квадрат . Это требует
арифметические операции над F q на каждом шаге, и, таким образом,
арифметические операции для всего алгоритма.
Метод II. Используя тот факт, что q -я степень является линейным отображением над F q, мы можем вычислить ее матрицу с помощью
операции. Затем на каждой итерации цикла вычислите произведение матрицы на вектор (с O (deg ( f ) 2 ) операциями). Это индуцирует общее количество операций в F q, которое равно
Таким образом, этот второй метод более эффективен и обычно предпочтительнее. Более того, матрица, которая вычисляется в этом методе, используется большинством алгоритмов для факторизации равной степени (см. Ниже); таким образом, использование его для факторизации с разной степенью экономит дополнительное время вычислений.
Факторизация с равной степенью
Алгоритм Кантора – Цассенхауза
В этом разделе мы рассмотрим факторизацию однозначного бесквадратного одномерного многочлена f степени n над конечным полем F q , которое имеет r ≥ 2 попарно различных неприводимых множителейкаждый степени d .
Сначала мы опишем алгоритм Кантора и Цассенхауса (1981), а затем вариант, который имеет немного лучшую сложность. Оба являются вероятностными алгоритмами, время выполнения которых зависит от случайного выбора ( алгоритмы Лас-Вегаса ) и имеют хорошее среднее время выполнения. В следующем разделе мы описываем алгоритм Шупа (1990), который также является алгоритмом факторизации равной степени, но является детерминированным. Все эти алгоритмы требуют нечетного порядка q поля коэффициентов. Дополнительные алгоритмы факторизации см., Например, в книге Кнута Искусство компьютерного программирования, том 2.
Алгоритм Алгоритм Кантора – Цассенхауза. Вход: Конечное поле F q нечетного порядка q . Нормированный на квадрат многочлена F в F д [ х ] степени п = й , который имеет r ≥ 2 неприводимых множителей степени d каждый. Выход: множество монических неприводимых множителей f .
Факторы: = { f }; в то время как Размер (Факторы) < r do, Выберем h в F q [ x ] с deg ( h ) < n наугад; для каждого u в Факторах с deg ( u )> d do если gcd ( g , u ) ≠ 1 и gcd ( g , u ) ≠ u , то Факторы: = Факторы ; endif; в конце концов Факторы возврата.
Корректность этого алгоритма основана на том факте, что кольцо F q [ x ] / f является прямым произведением полей F q [ x ] / f i, где f i пробегает неприводимые множители f . Поскольку все эти поля имеют q d элементов, компонента g в любом из этих полей равна нулю с вероятностью
Это означает, что полином gcd ( g , u ) является произведением множителей g, для которых компонента g равна нулю.
Было показано, что среднее количество итераций цикла while алгоритма меньше , что дает среднее количество арифметических операций в F q, которое равно. [2]
В типичном случае, когда d log ( q )> n , эта сложность может быть уменьшена до
выбрав h в ядре линейного отображения
и замена инструкции
от
Доказательство справедливости такое же, как и выше, с заменой прямого произведения полей F q [ x ] / f i прямым произведением их подполей с q элементами. Сложность раскладывается на для самого алгоритма, для вычисления матрицы линейного отображения (которая уже может быть вычислена в бесквадратной факторизации) и O ( n 3 ) для вычисления ее ядра. Можно отметить, что этот алгоритм работает также, если факторы имеют разную степень (в этом случае количество факторов r , необходимое для остановки цикла while, определяется как размерность ядра). Тем не менее, сложность немного лучше, если факторизация без квадратов выполняется до использования этого алгоритма (поскольку n может уменьшаться при факторизации без квадратов, это снижает сложность критических шагов).
Алгоритм Виктора Шупа
Как и алгоритмы предыдущего раздела, алгоритм Виктора Шупа представляет собой алгоритм факторизации равной степени. [3] В отличие от них, это детерминированный алгоритм. Однако на практике он менее эффективен, чем алгоритмы предыдущего раздела. Для алгоритма Шупа ввод ограничен полиномами над простыми полями F p .
Наихудшая временная сложность алгоритма Шупа имеет факторНесмотря на экспоненциальный характер, эта сложность намного лучше, чем у предыдущих детерминированных алгоритмов (алгоритм Берлекампа), в которых р как фактор. Однако существует очень мало полиномов, для которых время вычисления экспоненциально, а средняя временная сложность алгоритма полиномиальна отгде d - степень полинома, а p - количество элементов основного поля.
Пусть g = g 1 ... g k - искомая факторизация, где g i - различные монические неприводимые многочлены степени d . Пусть n = deg ( g ) = kd . Рассмотрим кольцо R = F д [ х ] / г и обозначим также х образ х в R . Кольцо R является прямым произведением полей R i = F q [ x ] / g i , и мы обозначим через p i естественный гомоморфизм из R на R i . Группа Галуа из R я над F д циклический порядка д , порожденное поле автоморфизме U → U р . Отсюда следует, что корни g i в R i равны
Как и в предыдущем алгоритме, этот алгоритм использует ту же подалгебру B из R в качестве алгоритма Берлекэмпа , иногда называют «Берлекемпа subagebra» и определяется как
Подмножество S в B называется разделяющим множеством, если для каждого 1 ≤ i < j ≤ k существует s ∈ S такое, что. В предыдущем алгоритме, разделяющее множество строится путем выбора случайным образом элементы S . В алгоритме Шупа разделяющее множество строится следующим образом. Пусть s в R [ Y ] таково, что
потом является разделяющим множеством, потому что для i = 1, ..., k (два монических многочлена имеют одинаковые корни). Поскольку g i попарно различны, для каждой пары различных индексов ( i , j ) по крайней мере один из коэффициентов s h будет удовлетворять
Имея разделяющий набор, алгоритм Шупа действует как последний алгоритм предыдущего раздела, просто заменяя инструкцию «выбрать произвольно h в ядре линейной карты."by" выбираем h + i с h в S и i в {1, ..., k −1} ".
Сложность времени
Как описано в предыдущих разделах, для факторизации по конечным полям существуют рандомизированные алгоритмы полиномиальной временной сложности (например, алгоритм Кантора-Цассенхауза). Также существуют детерминированные алгоритмы с полиномиальной средней сложностью (например, алгоритм Шупа).
Существование детерминированного алгоритма с полиномиальной сложностью наихудшего случая все еще остается открытой проблемой.
Тест неприводимости Рабина
Как и алгоритм факторизации различных степеней, алгоритм Рабина [4] основан на сформулированной выше лемме. Алгоритм факторизации разной степени проверяет каждые d не более половины степени входного полинома. Алгоритм Рабина использует то преимущество, что факторы не нужны для учета меньшего числа d . В остальном он аналогичен алгоритму факторизации с разной степенью. Это основано на следующем факте.
Пусть p 1 , ..., p k , - все простые делители числа n , и обозначим, для 1 ≤ i ≤ k многочлен f из F q [ x ] степени n неприводим в F q [ x ] тогда и только тогда, когда, для 1 ≤ i ≤ k , и f делит. Фактически, если f имеет множитель степени, не делящего n , то f не делит; если у f есть фактор степени деления n , то этот множитель делит хотя бы один из
Алгоритм Рабина Несводимости Test Input : унитарный многочлен F в F д [ х ] степени п , р 1 , ..., р K все различные простые делители п . Вывод : Либо « f неприводимо», либо « f приводимо». для j = 1 до k сделать ; для i = от 1 до k сделать ; g : = gcd ( f , h ); если g ≠ 1, то возвращаем « f сводимо» и STOP ; конец для ; ; если g = 0, то верните « f неприводимо», иначе верните « f является приводимым»
Основная идея этого алгоритма - вычислить начиная с самого маленького повторным возведением в квадрат или с использованием автоморфизма Фробениуса , а затем взять соответствующий НОД. Используя элементарную полиномиальную арифметику, вычисление матрицы автоморфизма Фробениуса требуетопераций в F q , вычисление
требуется O ( n 3 ) дальнейших операций, а самому алгоритму требуется O ( kn 2 ) операций, что в сумме даетоперации в F q . Использование быстрой арифметики (сложность для умножения и деления, и для вычисления НОД), вычисление повторным возведением в квадрат , а сам алгоритм , что в сумме дает операции в F q .
Смотрите также
- Алгоритм Берлекампа
- Алгоритм Кантора – Цассенхауза
- Полиномиальная факторизация
Рекомендации
- КЕМПФЕРТ, H (1969) О факторизации многочленов, Департамент математики, Государственный университет Огайо, Колумбус, Огайо 43210
- Шуп, Виктор (1996) Полиномы гладкости и факторизации над конечными полями, факультет компьютерных наук, Университет Торонто
- Фон Цур Гатен, Дж .; Панарио, Д. (2001). Факторинг полиномов по конечным полям: обзор . Журнал символических вычислений , том 31, выпуски 1-2, январь 2001 г., стр. 3-17.
- Гао Шухонг, Панарио Даниэль, Проверка и построение неприводимых многочленов над конечными полями, Департамент математических наук, Университет Клемсона, Южная Каролина, 29634–1907, США. и факультет информатики Университета Торонто, Канада M5S-1A4
- Виктор Шуп (1989) Новые алгоритмы поиска неприводимых многочленов над конечными полями Департамент компьютерных наук Висконсинский университет в Мэдисоне
- Геддес, Кейт О .; Czapor, Stephen R .; Лабан, Джордж (1992). Алгоритмы компьютерной алгебры . Бостон, Массачусетс: Kluwer Academic Publishers. С. xxii + 585. ISBN 0-7923-9259-0 .
Внешние ссылки
- Некоторые неприводимые многочлены http://www.math.umn.edu/~garrett/m/algebra/notes/07.pdf
- Теория поля и Галуа: http://www.jmilne.org/math/CourseNotes/FT.pdf
- Поле Галуа: http://designtheory.org/library/encyc/topics/gf.pdf
- Факторинг полиномов по конечным полям: http://www.science.unitn.it/~degraaf/compalg/polfact.pdf
Заметки
- ^ Christophe Reutenauer, Mots circaires et polynomes nonductibles , Ann. Sci. математика Квебека, том 12, № 2, стр. 275-285
- ^ Флажолет, Филипп; Steayaert, Жан-Марк (1982), Автоматы, языки и программирование , Конспекты лекций по вычислительной технике . Sci . , 140 ., Спрингер, С. 239-251, DOI : 10.1007 / BFb0012773 , ISBN 978-3-540-11576-2 Неизвестный параметр
|book-title=
игнорируется ( справка ) - ^ Виктор Шуп, О детерминированной сложности факторизации многочленов над конечными полями , Информационные письма 33: 261-267, 1990
- ^ Рабин, Майкл (1980). «Вероятностные алгоритмы в конечных полях». SIAM Journal on Computing . 9 (2): 273–280. CiteSeerX 10.1.1.17.5653 . DOI : 10.1137 / 0209024 .