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

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

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

例如，也许有超过ring of integers modulo prime number因式分解一些好的算法？

2015-04-05 petRUShka

为什么不使用matlab或类似的？ – 2015-04-05 20:46:20

@NickRosencrantz，通常我使用Sage Math来达到这个目的。但是现在我正在实现显着依赖于多项式因式分解的算法，并且还将GPU（基于Cuda或Opencl）作为目标平台。所以应该是C. – petRUShka 2015-04-05 20:50:57

也许运行牛顿法，寻找因子，多项式除法，重复。 – Makoto 2015-04-05 22:24:21

根据mathoverflow上的answer，Sage使用FLINT来进行因式分解。

FLINT（用于数论的快速库）是一个C库，用于支持数论中的计算。这也是一个数理论中的算法研究项目。

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

来源

2015-08-11 15:16:05 petRUShka

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

下一步将实施一个分解算法mod 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内核的运行版本，您都会更好。

来源

2015-04-12 20:18:21

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

回答

相关问题