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

редактировать
Вычислительный метод

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

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

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

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

Содержание

  • 1 Формулировка вопроса
  • 2 Факторизация примитивной части - содержимого
  • 3 Факторизация без квадратов
  • 4 Классические методы
    • 4.1 Получение линейных множителей
    • 4.2 Метод Кронекера
  • 5 Современные методы
    • 5.1 Факторинг по конечным полям
    • 5.2 Факторинг одномерных многочленов над целыми числами
    • 5.3 Факторинг над алгебраическими расширениями (метод Трагера)
  • 6 См. Также
  • 7 Библиография
  • 8 Дополнительная литература

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

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

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

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

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

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

и редукций:

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

Факторизация примитивной части-содержимого

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

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

Например,

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

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

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

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

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

cont (q) = cont (p) c, {\ displaystyle {\ text {cont}} (q) = {\ frac {{\ text {cont}} (p) } {c}},}\ текст {продолжение} (q) = \ frac {\ text {cont} (p)} {c},

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

Например,

x 5 3 + 7 x 2 2 + 2 x + 1 = 2 x 5 + 21 x 2 + 12 x + 6 6 {\ displaystyle {\ frac {x ^ {5 }} {3}} + {\ frac {7x ^ {2}} {2}} + 2x + 1 = {\ frac {2x ^ {5} + 21x ^ {2} + 12x + 6} {6}} }{\ 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1, 2, −1 или −2

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

4 × 4 × 8 = 128

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

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

построено из p (0) = 1 {\ displaystyle p (0) = 1}p (0) = 1 , p (1) = 3 {\ displaystyle p (1) = 3}p (1) = 3 и p (- 1) = 1 {\ displaystyle p (-1) = 1}p (-1) = 1 , множители f (x) {\ displaystyle f (x)}f (x) .

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

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

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

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

Разложение одномерных многочленов на множители целых

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

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

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

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

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

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

q (y) = ∏ i = 1 nqi (y) {\ displaystyle q (y) = \ prod _ {i = 1} ^ {n} q_ {i} (y)}q (y) = \ prod_ {i = 1} ^ {n} q_i (y)

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

L = Q [α] = Q [y] / q (y) = ∏ i Знак равно 1 N Q [y] / qi (y) {\ displaystyle L = \ mathbb {Q} [\ alpha] = \ mathbb {Q} [y] / q (y) = \ prod _ {i = 1} ^ {n} \ mathbb {Q} [y] / q_ {i} (y)}L = \ mathbb { Q} [\ alpha] = \ mathbb {Q} [y] / q (y) = \ prod_ {i = 1} ^ n \ mathbb {Q} [y] / q_i (y)

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

∏ i = 1 m K [x] / pi (x) {\ displaystyle \ prod _ {i = 1} ^ {m} K [x] / p_ {i} (x)}\ prod_ {i = 1} ^ m K [ х] / p_i (x)

где

p (x) = ∏ i = 1 mpi (x) {\ displaystyle p (x) = \ prod _ {i = 1} ^ {m} p_ {i} (x)}p (x) = \ prod_ {i = 1} ^ m p_i (x)

- факторизация p (x) {\ displaystyle p (x)}p (x) над K [x] {\ displaystyle K [x]}K [x] . Записав x ∈ L {\ displaystyle x \ in L}x \ in L и генераторы K {\ displaystyle K}K как многочлены от α {\ displaystyle \ alpha}\ alpha , мы можем определить вложения x {\ displaystyle x}x и K {\ displaystyle K}K в компоненты Q [y] / qi (y) = K [x] / pi (x) {\ displaystyle \ mathbb {Q} [y] / q_ {i} (y) = K [x] / p_ { i} (x)}\ mathbb {Q} [y] / q_i (y) = K [x] / p_i (x) . Найдя минимальный многочлен x {\ displaystyle x}x в этом кольце, мы вычислили pi (x) {\ displaystyle p_ {i} (x)}p_{i}(x), и, таким образом, разложили p (x) {\ displaystyle p (x)}p (x) на K. {\ displaystyle K.}K.

См. также

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

Дополнительная литература

  • K Альтофен, Эрих (1990), «Полиномиальная факторизация 1982-1986», в Д. В. Чудновском; Р.Д. Дженкс (ред.), Компьютеры в математике, Конспекты лекций по чистой и прикладной математике, 125, Marcel Dekker, Inc., CiteSeerX 10.1.1.68.7461
  • Кальтофен, Эрих (1992), «Полиномиальная факторизация 1987–1991» (PDF), Proceedings of Latin '92, Springer Lect. Notes Comput. Sci., 583, Springer, получено 14 октября 2012 г.
  • Ivanyos, Gabor; Марек, Карпинский; Саксена, Нитин (2009), "Схемы детерминированного полиномиального факторинга", Proc. ISSAC 2009: 191–198, arXiv : 0804.1974, doi : 10.1145 / 1576702.1576730, ISBN 9781605586090
Последняя правка сделана 2021-05-20 08:53:00
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте