Факторизация полиномов

Эта статья об алгоритмах факторизации. Информацию о методах бумаги и карандаша см. в разделе Факторизация § Полиномы .

В математике и компьютерной алгебре факторизация полиномов или полиномиальная факторизация выражает многочлен с коэффициентами в заданном поле или в целых числах как произведение неприводимых факторов с коэффициентами в той же области. Полиномиальная факторизация является одним из фундаментальных компонентов систем компьютерной алгебры .

Первый алгоритм полиномиальной факторизации был опубликован Теодором фон Шубертом в 1793 году. Леопольд Кронекер заново открыл алгоритм Шуберта в 1882 году и расширил его до многомерных многочленов и коэффициентов в алгебраическом расширении. Но большая часть знаний по этой теме не старше примерно 1965 года и первых систем компьютерной алгебры:

Когда давно известные алгоритмы с конечным шагом были впервые внедрены в компьютеры, они оказались крайне неэффективными. Тот факт, что практически любой одно- или многомерный полином степени до 100 и с коэффициентами умеренного размера (до 100 бит) может быть разложен современными алгоритмами за несколько минут компьютерного времени, показывает, насколько успешно эта проблема решалась в ходе последние пятнадцать лет. (Эрих Кальтофен, 1982)

В настоящее время современные алгоритмы и компьютеры могут быстро факторизовать одномерные многочлены степени более 1000, имеющие коэффициенты с тысячами цифр. Для этой цели, даже для факторизации рациональных чисел и числовых полей , фундаментальным шагом является факторизация многочлена по конечному полю .

Формулировка вопроса

Кольца полиномов над целыми числами или над полем являются уникальными областями факторизации . Это означает, что каждый элемент этих колец является произведением константы и произведением неприводимых многочленов (тех, которые не являются произведением двух непостоянных многочленов). Причем это разложение однозначно с точностью до умножения множителей на обратимые константы.

Факторизация зависит от базового поля. Например, фундаментальная теорема алгебры что каждый многочлен с комплексными коэффициентами имеет комплексные корни, подразумевает, что многочлен с целыми коэффициентами может быть разложен (с помощью алгоритмов поиска корней ) на линейные факторы над комплексным полем C. , которая утверждает , Аналогично, над полем действительных чисел неприводимые множители имеют степень не выше двух, тогда как существуют многочлены любой степени, неприводимые над полем рациональных Q. чисел

Вопрос о полиномиальной факторизации имеет смысл только для коэффициентов вычислимого поля , каждый элемент которого может быть представлен в компьютере и для которого существуют алгоритмы арифметических операций. Однако это не достаточное условие: Фрелих и Шепердсон приводят примеры таких полей, для которых не может существовать алгоритм факторизации.

Поля коэффициентов, для которых известны алгоритмы факторизации, включают поля простых чисел (т. е. поле рационального числа и поля целых чисел по модулю простого числа ) и их конечно порожденные расширения полей . Целочисленные коэффициенты также приемлемы. Классический метод Кронекера интересен лишь с исторической точки зрения; современные алгоритмы действуют последовательно:

• Бесквадратная факторизация
• Факторизация по конечным полям

и сокращения:

• От многомерного случая к одномерному .
• От коэффициентов в чисто трансцендентном расширении к многомерному случаю над основным полем (см. ниже ).
• От коэффициентов алгебраического расширения к коэффициентам основного поля (см. ниже ).
• От рациональных коэффициентов к целым коэффициентам (см. ниже ).
• От целых коэффициентов к коэффициентам в простом поле с p элементами для удачно выбранного p (см. ниже ).

Примитивная факторизация частей и содержания

См. Также: Содержание (алгебра) и лемма Гаусса (многочлен).

В этом разделе мы покажем, что факторизация по Q (рациональным числам) и по Z (целым числам), по сути, представляет собой одну и ту же проблему.

Содержимое наибольшим многочлена p ∈ Z [ X ], обозначаемое «cont( p )», с точностью до знака является общим делителем его коэффициентов. Примитивной частью p ) является primpart( p = p /cont( p ), который является примитивным полиномом с целыми коэффициентами. Это определяет факторизацию p в произведение целого числа и примитивного полинома. Эта факторизация уникальна с точностью до знака содержания. Обычно принято выбирать знак содержания так, чтобы старший коэффициент примитивной части был положительным.

Например,

$-10x^{2}+5x+5=(-5)(2x^{2}-x-1)\,$

представляет собой факторизацию на содержание и примитивную часть.

Любой многочлен q с рациональными коэффициентами можно записать

$q={\frac {p}{c}},$

где p ∈ Z [ X ] и c ∈ Z : достаточно взять в качестве c кратное всем знаменателям коэффициентов q (например, их произведение) и p = cq . Содержимое q определяется : как

${\text{cont}}(q)={\frac {{\text{cont}}(p)}{c}},$

а примитивная часть q — это часть p . Что касается многочленов с целыми коэффициентами, это определяет факторизацию в рациональное число и примитивный многочлен с целыми коэффициентами. Эта факторизация также единственна с точностью до выбора знака.

Например,

${\frac {x^{5}}{3}}+{\frac {7x^{2}}{2}}+2x+1={\frac {2x^{5}+21x^{2}+12x+6}{6}}$

представляет собой факторизацию на содержание и примитивную часть.

Гаусс доказал, что произведение двух примитивных многочленов также примитивно ( лемма Гаусса ). Это означает, что примитивный многочлен неприводим в рациональных числах тогда и только тогда, когда он неприводим в целых числах. Это также означает, что факторизация по рациональным числам многочлена с рациональными коэффициентами аналогична факторизации по целым числам его примитивной части. Аналогично, факторизация по целым числам многочлена с целыми коэффициентами является продуктом факторизации его примитивной части на факторизацию его содержимого.

Другими словами, вычисление целочисленного НОД сводит факторизацию многочлена по рациональным числам к факторизации примитивного многочлена с целыми коэффициентами, а факторизацию по целым числам - к факторизации целого числа и примитивного многочлена.

Все, что предшествует, остается верным, если Z заменить кольцом полиномов над полем F , а Q заменить полем рациональных функций над F от тех же переменных, с той лишь разницей, что «с точностью до знака» необходимо заменить на « с точностью до умножения на обратимую константу в F ". Это сводит факторизацию по чисто трансцендентному полевому расширению F к факторизации многомерных полиномов над F .

Бесквадратная факторизация

Основная статья: Бесквадратный полином

Если два и более множителя многочлена одинаковы, то многочлен кратен квадрату этого множителя. полинома Кратный множитель также является множителем производной (по любой из переменных, если их несколько).

Для одномерных полиномов несколько факторов эквивалентны множественным корням (в подходящем поле расширения). Для одномерных полиномов по рациональным числам (или, в более общем смысле, по полю с нулевой характеристикой ) алгоритм Юна использует это для эффективной факторизации многочлена на факторы, свободные от квадратов, то есть факторы, которые не кратны квадрату, выполняя последовательность Вычисления НОД, начинающиеся с НОД( f ( x ), f '( x )). Для факторизации исходного полинома достаточно факторизовать каждый бесквадратный фактор. Таким образом, факторизация без квадратов является первым шагом в большинстве алгоритмов полиномиальной факторизации.

Алгоритм Юна распространяет это на случай многомерного многомерного многомерного многочлена, рассматривая многомерный многочлен как одномерный многочлен над кольцом полиномов.

В случае многочлена над конечным полем алгоритм Юна применяется только в том случае, если степень меньше характеристики, поскольку в противном случае производная ненулевого многочлена может быть равна нулю (по полю с p элементами производная многочлен от x ^п всегда равен нулю). Тем не менее, последовательность вычислений НОД, начиная с полинома и его производной, позволяет вычислить разложение без квадратов; см. Полиномиальную факторизацию по конечным полям#Бесквадратная факторизация .

Классические методы

В этом разделе описаны хрестоматийные методы, которые могут оказаться удобными при ручных вычислениях. Эти методы не используются для компьютерных вычислений, поскольку они используют целочисленную факторизацию , которая в настоящее время медленнее, чем полиномиальная факторизация.

Два следующих метода начинаются с одномерного полинома с целыми коэффициентами для поиска факторов, которые также являются полиномами с целыми коэффициентами.

Получение линейных коэффициентов

Все линейные факторы с рациональными коэффициентами можно найти с помощью теста рационального корня . Если полином, подлежащий факторизации, равен $a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}$, то все возможные линейные факторы имеют вид $b_{1}x-b_{0}$, где $b_{1}$ является целочисленным коэффициентом $a_{n}$ и $b_{0}$ является целочисленным коэффициентом $a_{0}$. Все возможные комбинации целочисленных коэффициентов могут быть проверены на достоверность, и каждый действительный из них может быть вынесен на множители с помощью полиномиального деления в длину . Если исходный полином является произведением факторов, по крайней мере два из которых имеют степень 2 или выше, этот метод обеспечивает только частичную факторизацию; в противном случае факторизация завершена. В частности, если существует ровно один нелинейный фактор, это будет полином, оставшийся после факторизации всех линейных факторов. В случае кубического многочлена , если кубика вообще факторизуема, тест на рациональный корень дает полную факторизацию либо на линейный фактор и неприводимый квадратичный фактор, либо на три линейных фактора.

Метод Кронекера

Метод Кронекера направлен на разложение одномерных многочленов с целыми коэффициентами на многочлены с целыми коэффициентами.

В методе используется тот факт, что при оценке целочисленных полиномов в целочисленных значениях должны выдаваться целые числа. То есть, если $f(x)$ является многочленом с целыми коэффициентами, то $f(a)$является целым числом, как только a является целым числом. Существует только конечное число возможных целочисленных значений для фактора a . Так что если $g(x)$ является фактором $f(x),$ значение $g(a)$ должно быть одним из факторов $f(a).$

Если искать все факторы данной степени d , можно рассмотреть $d+1$ ценности, $a_{0},\ldots ,a_{d}$ для a , что дает конечное число возможностей для кортежа $(f(a_{0}),\ldots ,f(a_{d})).$ Каждый $f(a_{i})$ имеет конечное число делителей $b_{i,0},\ldots ,b_{i,k_{i}}$, и каждый $(d+1)$-кортеж, где $i^{\text{th}}$ запись является делителем $f(a_{i})$, то есть кортеж вида $(b_{0,j_{1}},\ldots ,b_{d,j_{d}})$, дает уникальный многочлен степени не более $d$, который можно вычислить полиномиальной интерполяцией . Каждый из этих полиномов можно проверить на предмет фактора путем полиномиального деления . Поскольку их было конечное число $a_{i}$ и каждый $f(a_{i})$имеет конечное число делителей, то таких кортежей конечное число. Итак, перебор позволяет найти все сомножители степени не выше d .

Например, рассмотрим

$f(x)=x^{5}+x^{4}+x^{2}+x+2$.

Если этот полином факторизуется по Z , то хотя бы один из его факторов $p(x)$ должно иметь степень две или меньше, поэтому $p(x)$однозначно определяется тремя значениями . Таким образом, мы вычисляем три значения $f(0)=2$, $f(1)=6$ и $f(-1)=2$. Если одно из этих значений равно 0, мы имеем линейный коэффициент. Если значения ненулевые, мы можем перечислить возможные факторизации для каждого. Теперь 2 может учитываться только как

1×2, 2×1, (-1)×(-2) или (-2)×(-1).

Следовательно, если существует коэффициент целочисленного полинома второй степени, он должен принимать одно из значений

р (0) = 1, 2, -1 или -2

и аналогично для p (1). Существует восемь факторизаций 6 (по четыре для 1×6 и 2×3), что в общей сложности дает 4×4×8 = 128 возможных троек ( p (0), p (1), p (−1)), половину из которых можно отбросить как негативы другой половины. Таким образом, нам необходимо проверить 64 явных целочисленных полинома. $p(x)=ax^{2}+bx+c$ как возможные факторы $f(x)$. Их тщательное тестирование показывает, что

$p(x)=x^{2}+x+1$

построенный из ( g (0), g (1), g (−1)) = (1,3,1) множителей $f(x)$.

Разделив f ( x ) на p ( x ), получим другой коэффициент $q(x)=x^{3}-x+2$, так что $f(x)=p(x)q(x)$. Теперь можно провести рекурсивное тестирование, чтобы найти факторы p ( x ) и q ( x ), в данном случае используя тест на рациональный корень. Оказывается, они оба неприводимые, поэтому неприводимая факторизация f ( x ) такова:

$f(x)=p(x)q(x)=(x^{2}+x+1)(x^{3}-x+2).$

Современные методы

Факторинг по конечным полям

Основные статьи: Факторизация полиномов над конечными полями , алгоритм Берлекампа и алгоритм Кантора – Зассенхауза.

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

Если $f(x)$ является одномерным полиномом над целыми числами, который считается свободным от содержания и квадратов , все начинается с вычисления границы $B$ такой, что любой фактор $g(x)$ имеет коэффициенты абсолютного значения, ограниченные $B$. Таким образом, если $m$ целое число, большее, чем $2B$, и если $g(x)$ известно по модулю $m$, затем $g(x)$ может быть восстановлен из его мода изображения $m$.

Алгоритм Цассенхауза действует следующим образом. Сначала выберите простое число $p$ такое, что образ $f(x){\bmod {p}}$ остается бесквадратным и имеет ту же степень, что и $f(x)$. Тогда фактор $f(x){\bmod {p}}$. Это дает целочисленные полиномы $f_{1}(x),\ldots ,f_{r}(x)$ чей продукт соответствует $f(x){\bmod {p}}$. Далее примените лифтинг Hensel ; это обновляет $f_{i}(x)$ таким образом, чтобы их продукт соответствовал $f(x){\bmod {p}}^{a}$, где $a$ достаточно велик, чтобы $p^{a}$ превышает $2B$: таким образом каждый $f_{i}(x)$соответствует четко определенному целочисленному многочлену. по модулю $p^{a}$, полином $f(x)$ имеет $2^{r}$ факторы (до единиц): продукты всех подмножеств $\{f_{1}(x),\ldots ,f_{r}(x)\}{\bmod {p}}^{a}$. Эти факторы по модулю $p^{a}$ не обязательно должны соответствовать «истинным» факторам $f(x)$ в $\mathbb {Z} [x]$, но мы можем легко проверить их делением на $\mathbb {Z} [x]$. Таким образом, все неприводимые истинные факторы можно найти, проверив не более $2^{r}$ случаев, сведенных к $2^{r-1}$случаях, пропуская дополнения. Если $f(x)$ сокращаемо, то число случаев сокращается еще больше за счет удаления тех $f_{i}(x)$которые появляются в уже найденном истинном факторе. Алгоритм Цассенхауза быстро обрабатывает каждый случай (каждое подмножество), однако в худшем случае он рассматривает экспоненциальное количество случаев.

Первый алгоритм с полиномиальным временем для факторизации рациональных многочленов был открыт Ленстрой, Ленстрой и Ловасом и представляет собой применение алгоритма сокращения решеточного базиса Ленстры-Ленстры-Ловаса (LLL) ( Lenstra, Lenstra & Lovász 1982 ). Упрощенная версия алгоритма факторизации LLL выглядит следующим образом: вычислить комплексный (или p -адический) корень α многочлена $f(x)$ с высокой точностью, затем используйте алгоритм сокращения базиса решетки Ленстры-Ленстры-Ловаса, чтобы найти приближенную линейную зависимость между 1, α , α ² , а ³ , . . . с целочисленными коэффициентами, которые могут быть точной линейной зависимостью и полиномиальным коэффициентом $f(x)$. Можно определить границу точности, которая гарантирует, что этот метод даст либо фактор, либо доказательство неприводимости. Хотя этот метод завершается за полиномиальное время, на практике он не используется, поскольку решетка имеет большую размерность и огромные элементы, что замедляет вычисления.

Экспоненциальная сложность алгоритма Цассенхауза обусловлена ​​комбинаторной проблемой: как выбрать правильные подмножества $f_{1}(x),\ldots ,f_{r}(x)$. Современные реализации факторинга работают аналогично Цассенхаузу, за исключением того, что комбинаторная задача преобразуется в решеточную задачу, которая затем решается с помощью LLL. В этом подходе LLL используется не для вычисления коэффициентов факторов, а для вычисления векторов с $r$ записи в {0,1}, которые кодируют подмножества $f_{1}(x),\ldots ,f_{r}(x)$ соответствующие неприводимым истинным факторам.

Трагера

Мы можем факторизовать многочлен $p(x)\in K[x]$, где поле $K$ является конечным расширением $\mathbb {Q}$. Во-первых, используя факторизацию без квадратов , мы можем предположить, что полином не содержит квадратов. Далее мы определяем факторкольцо $L=K[x]/p(x)$ степени $n=[L:\mathbb {Q} ]=\deg p(x)\,[K:\mathbb {Q} ]$; это не поле, если только $p(x)$ неприводимо, но является приведенным кольцом, поскольку $p(x)$бесквадратен. Действительно, если

$p(x)=\prod _{i=1}^{m}p_{i}(x)$

— желаемая факторизация p ( x ), кольцо однозначно разлагается на поля как:

$L=K[x]/p(x)\cong \prod _{i=1}^{m}K[x]/p_{i}(x).$

Мы найдем это разложение, не зная факторизации. Во-первых, мы пишем L явно как алгебру над $\mathbb {Q}$: мы выбираем случайный элемент $\alpha \in L$, который генерирует $L$ над $\mathbb {Q}$с высокой вероятностью по теореме о примитивном элементе . Если это так, мы можем вычислить минимальный полином $q(y)\in \mathbb {Q} [y]$ из $\alpha$ над $\mathbb {Q}$, найдя $\mathbb {Q}$-линейная связь между 1, a , . . . , а ^н . Используя алгоритм факторизации для рациональных многочленов, мы факторизуем неприводимые в $\mathbb {Q} [y]$:

$q(y)=\prod _{i=1}^{n}q_{i}(y).$

Таким образом мы имеем:

$L\cong \mathbb {Q} [y]/q(y)\cong \prod _{i=1}^{n}\mathbb {Q} [y]/q_{i}(y),$

где $\alpha$ соответствует $y\leftrightarrow (y,y,\ldots ,y)$. Это должно быть изоморфно предыдущему разложению $L$.

Генераторы L — это x вместе с генераторами $K$ над $\mathbb {Q}$; записав их в виде многочленов в $\alpha$, мы можем определить вложения $x$ и $K$ в каждый компонент $\mathbb {Q} [y]/q_{i}(y)=K[x]/p_{i}(x)$. Найдя минимальный полином $x$ в $\mathbb {Q} [y]/q_{i}(y)$, мы вычисляем $p_{i}(x)$, и, следовательно, фактор $p(x)$ над $K.$

Численная факторизация

«Численная факторизация» обычно относится к факторизации многочленов с действительными или комплексными коэффициентами, коэффициенты которых известны только приблизительно, обычно потому, что они представлены как с плавающей запятой числа .

Для одномерных полиномов с комплексными коэффициентами факторизацию можно легко свести к численному вычислению корней и кратностей полиномов .

В многомерном случае случайное бесконечно малое возмущение коэффициентов с вероятностью единица дает неприводимый многочлен , даже если начинать с многочлена со многими факторами. Итак, сам смысл числовой факторизации нуждается в точном разъяснении.

Позволять $p$ быть многочленом с комплексными коэффициентами с неприводимой факторизацией

$p=\alpha p_{1}^{m_{1}}\cdots p_{k}^{m_{k}}$

где $\alpha \in C$ и факторы $p_{1},\ldots ,p_{k}$являются неприводимыми многочленами с комплексными коэффициентами. Предположим, что $p$ аппроксимируется полиномом ${\tilde {p}}$ коэффициенты которых близки к коэффициентам $p$. Точная факторизация ${\tilde {p}}$бессмысленно, поскольку оно, вообще говоря, неприводимо. Существует несколько возможных определений того, что можно назвать числовой факторизацией ${\tilde {p}}.$

Если $k$ и $m_{i}$известны, приближенная факторизация состоит в нахождении многочлена, близкого к ${\tilde {p}}$это факторы, как указано выше. Если не знать схему факторизации, выявив $m_{1},\ldots ,m_{k}$становится необходимым. Например, количество неприводимых множителей многочлена равно нулю его матрицы Руперта. Таким образом, кратности $m_{1},\ldots ,m_{k}$ может быть идентифицирован путем безквадратной факторизации посредством численного вычисления НОД и выявления ранга на матрицах Руперта.

Было разработано и реализовано несколько алгоритмов численной факторизации, что является предметом постоянных исследований.

См. также

• Факторизация § Полиномы для элементарных эвристических методов и явных формул
• Полиномы Суиннертона-Дайера — семейство полиномов, имеющих наихудшее время выполнения для метода Цассенхауза.

Библиография

• Фрелих, А.; Шеферсон, Дж. К. (1955), «О факторизации полиномов за конечное число шагов», Mathematische Zeitschrift , 62 (1): 331–334, doi : 10.1007/BF01180640 , ISSN   0025-5874 , S2CID   119955899
• Трагер, Б.М. (1976). «Алгебраический факторинг и интеграция рациональных функций». Материалы третьего симпозиума ACM по символьным и алгебраическим вычислениям - SYMSAC '76 . стр. 219–226. дои : 10.1145/800205.806338 . ISBN  9781450377904 . S2CID   16567619 .
• Бернар Бозами, Пер Энфло , Пол Ван (октябрь 1994 г.). «Количественные оценки полиномов от одной или нескольких переменных: от анализа и теории чисел к символическим и массово параллельным вычислениям». Журнал «Математика» . 67 (4): 243–257. дои : 10.2307/2690843 . JSTOR   2690843 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка ) (доступно читателям со степенью бакалавра математики)
• Коэн, Анри (1993). Курс вычислительной алгебраической теории чисел . Тексты для аспирантов по математике. Том. 138. Берлин, Нью-Йорк: Springer-Verlag . ISBN  978-3-540-55640-4 . МР   1228206 .
• Кальтофен, Эрих (1982), «Факторизация полиномов», у Б. Бухбергера; Р. Лоос; Дж. Коллинз (ред.), Компьютерная алгебра , издательство Springer, стр. 101–111. 95–113, CiteSeerX   10.1.1.39.7916
• Кнут, Дональд Э. (1997). «4.6.2 Факторизация полиномов». Получисловые алгоритмы . Искусство компьютерного программирования . Том. 2 (Третье изд.). Ридинг, Массачусетс: Аддисон-Уэсли. стр. 439–461, 678–691. ISBN  978-0-201-89684-8 .
• Ленстра, АК ; Ленстра, HW; Ловас, Ласло (1982). «Факторизация полиномов с рациональными коэффициентами». Математические Аннален . 261 (4): 515–534. CiteSeerX   10.1.1.310.318 . дои : 10.1007/BF01457454 . ISSN   0025-5831 . МР   0682664 . S2CID   5701340 .
• Ван дер Варден , Алгебра (1970), пер. Блюм и Шуленбергер, Фредерик Унгар.

Дальнейшее чтение

• Кальтофен, Эрих (1990), «Полиномиальная факторизация 1982–1986», у Д.В. Чудновского; Р.Д. Дженкс (ред.), Компьютеры в математике , Конспекты лекций по чистой и прикладной математике, том. 125, Марсель Деккер, Inc., CiteSeerX   10.1.1.68.7461
• Кальтофен, Эрих (1992), «Полиномиальная факторизация 1987–1991» (PDF) , Proceedings of Latin '92 , Springer Lect. Примечания Вычисл. наук, том. 583, Springer , получено 14 октября 2012 г.
• Иваньос, Габор; Марек, Карпински; Саксена, Нитин (2009). «Схемы детерминированного полиномиального факторинга». Материалы международного симпозиума по символьным и алгебраическим вычислениям 2009 года . стр. 191–198. arXiv : 0804.1974 . дои : 10.1145/1576702.1576730 . ISBN  9781605586090 . S2CID   15895636 .