Быстрая факторизация полинома с целыми коэффициентами

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

Например, я хочу разложить 4*x^6 + 20*x^5 + 29*x^4 - 14*x^3 - 71*x^2 - 48*x как (2*x^4 + 7*x^3 + 4*x^2 - 13*x - 16)*(2*x + 3)*x.

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

Я собираюсь использовать язык программирования C.

Например, могут быть некоторые хорошие алгоритмы для полиномиальной факторизации над кольцом целых чисел по модулю простого числа?

Ответ 1

В соответствии с этим answer в mathoverflow Sage использует FLINT делать факторизацию.

FLINT (быстрая библиотека для теории чисел) является библиотекой C в поддержку вычислений в теории чисел. Это также исследовательский проект в алгоритмы в теории чисел.

Таким образом, можно смотреть и даже использовать реализацию алгоритмов декомпозиции в той хорошо проверенной и стабильной библиотеке.

Ответ 2

Так как Sage является свободным и открытым исходным кодом, вы должны найти алгоритм, который использует Sage, а затем вызвать его или, в худшем случае, повторно реализовать его на C. Однако, если вы действительно должны написать процедуру с нуля, это что бы я сделал: сначала найдите gcd всех коэффициентов и разделите это, что делает ваш полиномиальный "контент свободным". Тогда возьмем производную и найдем многочлен gcd исходного многочлена и его производной. Возьмите этот множитель из исходного многочлена полиномиальным делением, которое разбивает вашу проблему на две части: факторинг без содержания, квадратный свободный многочлен (p/gcd (p, p ')) и факторинг другого многочлена (gcd (p, p ')), которые могут быть не квадратными. Для последнего начинайте сначала, пока вы не уменьшите проблему до факторинга одного или нескольких бессодержащих квадратичных полиномов.

Следующим шагом будет реализация алгоритма факторизации mod p. Алгоритм Берлекампа, вероятно, самый простой, хотя Кантор-Зассенхаус - это современное состояние.

Наконец, примените алгоритм Цассенхауза к коэффициенту над целыми числами. Если вы обнаружите, что он слишком медленный, его можно улучшить с помощью "алгоритма восстановления решетки решетки Ленстра-Ленстра-Ловаша". http://en.wikipedia.org/wiki/Factorization_of_polynomials#Factoring_univariate_polynomials_over_the_integers

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