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

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

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

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

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

Постановка вопроса

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

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

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

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

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

и скидки:

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

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

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

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

Например,

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

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

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

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

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

{displaystyle {ext {cont}} (q) = {frac {{ext {cont}} (p)} {c}},}

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

Например,

{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.

Факторизация без квадратов

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

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

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

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

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

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

Все линейные множители с рациональными коэффициентами можно найти с помощью рациональный корень. Если факторизуемый многочлен равен ${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}}$ . Все возможные комбинации целочисленных факторов могут быть проверены на достоверность, и каждое действительное значение может быть исключено с помощью полиномиальное деление в столбик. Если исходный полином является произведением множителей, по крайней мере, два из которых имеют степень 2 или выше, этот метод обеспечивает только частичную факторизацию; в противном случае факторизация завершена. В частности, если существует ровно один нелинейный множитель, это будет полином, оставшийся после того, как все линейные множители были разложены на множители. В случае кубический многочлен, если кубика вообще факторизуема, критерий рационального корня дает полную факторизацию либо на линейный множитель и неприводимый квадратичный множитель, либо на три линейных множителя.

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

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

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

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

.

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

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

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

1, 2, −1 или −2

в ${displaystyle x = 0}$ , а также на ${displaystyle x = -1}$ . Существует восемь различных способов разложить 6 (по одному на каждый делитель 6), так что есть

4×4×8 = 128

возможные комбинации, половина из которых может быть отброшена как отрицание другой половины, что соответствует 64 возможным целочисленным многочленам второй степени, которые необходимо проверить. Это единственные возможные целочисленные полиномиальные множители ${displaystyle f (x)}$ . Их исчерпывающее тестирование показывает, что

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

построен из ${displaystyle p (0) = 1}$ , ${displaystyle p (1) = 3}$ и ${displaystyle p (-1) = 1}$ , факторы ${displaystyle f (x)}$ .

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

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

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

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

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

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

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

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

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

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

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

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

над ${displaystyle mathbb {Q} [y]}$ , определяем, что

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

(Заметь ${displaystyle L}$ это уменьшенное кольцо поскольку ${displaystyle p (x)}$ без квадратов), где ${displaystyle alpha}$ соответствует элементу ${displaystyle (y, y, ldots, y)}$ . Обратите внимание, что это единственное разложение ${displaystyle L}$ как продукт полей. Следовательно, это разложение совпадает с

{displaystyle prod _ {i = 1} ^ {m} K [x] / p_ {i} (x)}

куда

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

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

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

Факторизация § Многочлены, для элементарных эвристических методов и явных формул

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

^ FT Schubert: De Inventione Divisorum Nova Acta Academiae Scientiarum Petropolitanae v.11, p. 172–182 (1793)
^ Пример степени 2401, занимающей 7,35 секунды, можно найти в Разделе 4 в: Hart, van Hoeij, Novocin: Практическое полиномиальное разложение на множители за полиномиальное время Труды ISSAC'2011, с. 163-170 (2011).
^ Ван дер Варден, Разделы 5.4 и 5.6
^ М. ван Хойдж: Факторинг многочленов и задача о рюкзаке. Журнал теории чисел, 95, 167-189, (2002).

Fröhlich, A .; Шеферсон, Дж. К. (1955), "О факторизации многочленов за конечное число шагов", Mathematische Zeitschrift, 62 (1): 331–334, Дои:10.1007 / BF01180640, ISSN 0025-5874
Трагер, Б. (1976), «Алгебраический факторинг и интеграция рациональных функций», Proc. SYMSAC 76, Symsac '76: 219–226, Дои:10.1145/800205.806338
Бернар Бозами, Пер Энфло, Пол Ван (октябрь 1994 г.). «Количественные оценки многочленов от одной или нескольких переменных: от анализа и теории чисел до символьных и массово-параллельных вычислений». Математический журнал. 67 (4): 243–257. Дои:10.2307/2690843. JSTOR 2690843.CS1 maint: несколько имен: список авторов (связь) CS1 maint: ref = harv (связь) (доступно для читателей с высшим математическим образованием)
Коэн, Анри (1993). Курс вычислительной алгебраической теории чисел. Тексты для выпускников по математике. 138. Берлин, Нью-Йорк: Springer-Verlag. ISBN 978-3-540-55640-4. МИСТЕР 1228206.CS1 maint: ref = harv (связь)
Кальтофен, Эрих (1982), "Факторизация многочленов", у Б. Бухбергера; Р. Лоос; Г. Коллинз (ред.), Компьютерная алгебра, Springer Verlag, стр. 95–113, CiteSeerX 10.1.1.39.7916
Кнут, Дональд Э (1997). «4.6.2 Факторизация многочленов». Получисловые алгоритмы. Искусство программирования. 2 (Третье изд.). Ридинг, Массачусетс: Эддисон-Уэсли. С. 439–461, 678–691. ISBN 978-0-201-89684-8.
Ленстра, А.К.; Lenstra, H.W .; Ловас, Ласло (1982). «Факторинг многочленов с рациональными коэффициентами». Mathematische Annalen. 261 (4): 515–534. CiteSeerX 10.1.1.310.318. Дои:10.1007 / BF01457454. ISSN 0025-5831. МИСТЕР 0682664.CS1 maint: ref = harv (связь)
Ван дер Варден, Алгебра (1970), пер. Блюм и Шуленбергер, Фредерик Ангар.

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

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

[1] FT Schubert: De Inventione Divisorum Nova Acta Academiae Scientiarum Petropolitanae v.11, p. 172–182 (1793)

[2] Пример степени 2401, занимающей 7,35 секунды, можно найти в Разделе 4 в: Hart, van Hoeij, Novocin: Практическое полиномиальное разложение на множители за полиномиальное время Труды ISSAC'2011, с. 163-170 (2011).

[3] Ван дер Варден, Разделы 5.4 и 5.6

[4] М. ван Хойдж: Факторинг многочленов и задача о рюкзаке. Журнал теории чисел, 95, 167-189, (2002).

[1]

[2]

[3]

[4]