Факторизация многочленов

Метод расчета

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

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

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

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

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

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

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

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

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

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

и скидки:

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

Примитивная часть–разложение содержимого

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

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

Например,

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

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

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

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

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

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

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

Например,

${\displaystyle {\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 ^p всегда равна нулю). Тем не менее, последовательность вычислений НОД, начиная с многочлена и его производной, позволяет вычислить бесквадратное разложение; см. Разложение многочленов над конечными полями#Разложение на бесквадратные множители .

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

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

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

Получение линейных множителей

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

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

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

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

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

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

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

Если этот многочлен факторизуется по Z , то по крайней мере один из его факторов должен иметь степень два или меньше, поэтому однозначно определяется тремя значениями . Таким образом, мы вычисляем три значения , и . Если одно из этих значений равно 0, мы имеем линейный фактор. Если значения не равны нулю, мы можем перечислить возможные факторизации для каждого. Теперь 2 может факторизоваться только как ${\displaystyle p(x)}$ ${\displaystyle p(x)}$ ${\displaystyle f(0)=2}$ ${\displaystyle f(1)=6}$ ${\displaystyle f(-1)=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 явных целочисленных многочлена как возможные множители . Их исчерпывающая проверка показывает, что ${\displaystyle p(x)=ax^{2}+bx+c}$ ${\displaystyle f(x)}$

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

построенный из ( g (0), g (1), g (−1)) = (1,3,1) факторов . ${\displaystyle f(x)}$

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

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

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

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

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

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

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

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

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

Факторизация по алгебраическим расширениям (метод Трегера)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть — многочлен с комплексными коэффициентами с неприводимым разложением ${\displaystyle p}$

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

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

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

Было разработано и реализовано несколько алгоритмов для числовой факторизации как текущего предмета исследования. ^{[8] [9]}

Смотрите также

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

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

1. FT Шуберт: De Inventione Divisorum Nova Acta Academiae Scientiarum Petropolitanae v.11, стр. 172–182 (1793)
2. Кальтофен (1982)
3. Пример степени 2401, требующей 7,35 секунд, можно найти в разделе 4 в: Hart, van Hoeij, Novocin: Practical Polynomial Factoring in Polynomial Time ISSAC'2011 Proceedings, стр. 163–170 (2011).
4. Фрелих, А.; Шепердсон, Дж. К. (1955). «О факторизации многочленов за конечное число шагов». Mathematische Zeitschrift . 62 (1): 331–334. дои : 10.1007/bf01180640. ISSN  0025-5874. S2CID  119955899.
5. Ван дер Варден , разделы 5.4 и 5.6.
6. М. ван Хой: Факторизация многочленов и задача о рюкзаке. Журнал теории чисел, 95, 167–189, (2002).
7. Рупперт, В. (1999). «Приводимость многочленов f(x,y)». J. Number Theory . 77 : 62–70. arXiv : math/9808021 . doi :10.1006/jnth.1999.2381. S2CID  14316123.

   Шейкер, Х. (2009). «Топология и факторизация многочленов». Math. Scand . 104 : 51–59. arXiv : 0704.3363 . doi :10.7146/math.scand.a-15084. S2CID  14121840.

8. Например: W. Wu и Z. Zeng (2017). «Численная факторизация многочленов». Основы вычислительной математики . 17 : 259–286. arXiv : 2103.04888 . doi : 10.1007/s10208-015-9289-1. S2CID  254171366.
9. E. Kaltofen, JP May, Z. Yang и L. Zhi (2008). «Приближенная факторизация многомерных полиномов с использованием сингулярного разложения». J. Symbolic Comput . 43 (5): 359–376. doi : 10.1016/j.jsc.2007.11.005 .{{cite journal}}: CS1 maint: multiple names: authors list (link)

• Фрелих, А.; Шеферсон, Дж. К. (1955), «О факторизации полиномов за конечное число шагов», Mathematische Zeitschrift , 62 (1): 331–334, doi : 10.1007/BF01180640, ISSN  0025-5874, S2CID  119955899
• Trager, BM (1976). "Алгебраическая факторизация и рациональное функциональное интегрирование". Труды третьего симпозиума ACM по символическим и алгебраическим вычислениям - SYMSAC '76. стр. 219–226. doi :10.1145/800205.806338. ISBN 9781450377904. S2CID  16567619.
• Бернар Бозами, Пер Энфло , Пол Ванг (октябрь 1994 г.). «Количественные оценки полиномов от одной или нескольких переменных: от анализа и теории чисел до символических и массивно-параллельных вычислений». Mathematics Magazine . 67 (4): 243–257. doi :10.2307/2690843. JSTOR  2690843.{{cite journal}}: CS1 maint: multiple names: authors list (link)(доступно для читателей, имеющих степень бакалавра по математике)
• Коэн, Анри (1993). Курс вычислительной алгебраической теории чисел . Graduate Texts in Mathematics. Том 138. Берлин, Нью-Йорк: Springer-Verlag . ISBN 978-3-540-55640-4. МР  1228206.
• Кальтофен, Эрих (1982), «Факторизация полиномов», у Б. Бухбергера; Р. Лоос; Г. Коллинз (ред.), Компьютерная алгебра , Springer Verlag, стр. 95–113, CiteSeerX  10.1.1.39.7916
• Кнут, Дональд Э. (1997). "4.6.2 Факторизация многочленов". Получисленные алгоритмы . Искусство программирования . Том 2 (Третье изд.). Рединг, Массачусетс: Addison-Wesley. С. 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. MR  0682664. S2CID  5701340.
• Ван дер Варден , Алгебра (1970), пер. Блюм и Шуленбергер, Фредерик Унгар.

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

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