整数系数多项式的快速分解

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编程语言。

例如，也许有关于在模质素数的整数环上进行多项式分解的良好算法吗？

- petRUShka

---

为什么不使用Matlab或类似的软件？ - Niklas Rosencrantz

@NickRosencrantz，通常我使用Sage Math来实现这样的目标。但是现在我正在设计一个明显依赖于多项式因式分解的算法，并且还有GPU（基于Cuda或Opencl）作为目标平台。所以应该使用C语言。 - petRUShka

可能运行牛顿法，找到因子，进行多项式除法，重复执行。 - Makoto

你必须意识到，在 F(Z, x) 上的因式分解不能比在 Z 上的因式分解更快。下一步是投射一个 Viète 幽灵，并对系数进行因式分解。无论如何，祝你好运。 - user58697

@petRUShka：你能分享一下你的C代码吗？ - Silicomancer

Answer 1

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

下一步将是实现模p的分解算法。Berlekamp算法可能是最简单的，虽然Cantor-Zassenhaus是当前最先进的算法。

最后，使用Zassenhaus算法来对整数进行因式分解。如果您发现速度过慢，可以使用“Lenstra-Lenstra-Lovasz格基约简算法”进行改进。http://en.wikipedia.org/wiki/Factorization_of_polynomials#Factoring_univariate_polynomials_over_the_integers 正如您所看到的，这一切都相当复杂，并且依赖于抽象代数学的许多理论。最好使用与Sage相同的库，或重新实现Sage的实现，甚至只需从程序内部调用运行中的Sage内核即可。

- Edward Doolittle

Answer 2

根据mathoverflow上的这个答案，Sage使用FLINT进行因式分解。

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

所以可以查看甚至使用该库中已经经过充分测试和稳定的分解算法的实现。

- petRUShka