c - 具有整数系数的多项式的快速因式分解

Question

我想在整数环上快速分解多项式（原始多项式具有整数系数，所有因子都具有整数系数）。

例如我想分解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 编程语言。

例如，也许有一些很好的算法可以对整数环模素数进行多项式分解？

Answer 1

由于 Sage 是免费和开源的，你应该能够找到 Sage 使用的算法，然后调用它，或者最坏的情况是用 C 重新实现它。但是，如果你真的必须从头开始编写一个过程，这就是我想要的做：首先找到所有系数的 gcd 并将其除以，这使您的多项式“无内容”。然后取导数，求原多项式及其导数的多项式gcd。通过多项式除法从原始多项式中取出该因子，这会将您的问题分为两部分：分解一个无内容、无平方的多项式 (p/gcd(p,p'))，以及分解另一个多项式 (gcd(p, p')) 可能不是正方形的。对于后者，从头开始，直到您将问题简化为分解一个或多个无内容、无平方多项式。

下一步将是实现一个因式分解算法 mod p。Berlekamp 的算法可能是最简单的，尽管 Cantor-Zassenhaus 是最先进的。

最后，应用 Zassenhaus 算法对整数进行因式分解。如果您发现它太慢，可以使用“Lenstra-Lenstra-Lovasz lattice base reduction algorithm”进行改进。http://en.wikipedia.org/wiki/Factorization_of_polynomials#Factoring_univariate_polynomials_over_the_integers

正如你所看到的，这一切都相当复杂，并且依赖于抽象代数的大量理论。你最好使用 Sage 使用的同一个库，或者重新实现 Sage 实现，甚至只是从你的程序中调用 Sage 内核的运行版本。

Answer 2

根据这个关于 mathoverflow的答案， Sage使用FLINT进行分解。

FLINT（数论快速库）是一个支持数论计算的 C 库。它也是数论算法的研究项目。

因此，可以在经过良好测试且稳定的库中查看甚至使用分解算法的实现。