整数系数多项式的快速因式分解
Fast factorization of polynomial with integers coefficients
我想快速分解整数环上的多项式（原多项式有整数系数，所有因子都有整数系数）。
例如我想将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 的多项式因式分解的好算法？
由于 Sage 是免费和开源的，您应该能够找到 Sage 使用的算法然后调用它，或者最坏的情况是用 C 重新实现它。但是，如果您真的必须从头开始编写程序，这就是我要做的：首先找到所有系数的 gcd 并将其除掉，这使得你的多项式 "content free"。然后求导，求原多项式及其导数的多项式gcd。通过多项式除法从原始多项式中取出该因子，这将您的问题分为两部分：分解一个无内容、无平方多项式 (p/gcd(p,p'))，并分解另一个多项式 (gcd( p,p')) 可能不是正方形。对于后者，从头开始，直到将问题简化为分解一个或多个无内容、无平方的多项式。
下一步将是实现分解算法 mod p。 Berlekamp 的算法可能是最简单的，尽管 Cantor-Zassenhaus 是最先进的。
最后，应用 Zassenhaus 算法对整数进行因式分解。如果您发现它太慢，可以使用 "Lenstra-Lenstra-Lovasz lattice basis reduction algorithm" 进行改进。 http://en.wikipedia.org/wiki/Factorization_of_polynomials#Factoring_univariate_polynomials_over_the_integers
如您所见，这一切都相当复杂，并且依赖于抽象代数中的大量理论。您最好使用与 Sage 相同的库，或者重新实现 Sage 实现，或者甚至只是从您的程序中调用 运行 版本的 Sage 内核。
据此answer on mathoverflow, Sage uses FLINT做因式分解。
FLINT (Fast Library for Number Theory) is a C library in support of
computations in number theory. It's also a research project into
algorithms in number theory.
因此可以在经过充分测试且稳定的库中查看甚至使用分解算法的实现。
我想快速分解整数环上的多项式（原多项式有整数系数，所有因子都有整数系数）。
例如我想将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 的多项式因式分解的好算法？
由于 Sage 是免费和开源的，您应该能够找到 Sage 使用的算法然后调用它，或者最坏的情况是用 C 重新实现它。但是，如果您真的必须从头开始编写程序，这就是我要做的：首先找到所有系数的 gcd 并将其除掉，这使得你的多项式 "content free"。然后求导，求原多项式及其导数的多项式gcd。通过多项式除法从原始多项式中取出该因子，这将您的问题分为两部分：分解一个无内容、无平方多项式 (p/gcd(p,p'))，并分解另一个多项式 (gcd( p,p')) 可能不是正方形。对于后者，从头开始，直到将问题简化为分解一个或多个无内容、无平方的多项式。
下一步将是实现分解算法 mod p。 Berlekamp 的算法可能是最简单的，尽管 Cantor-Zassenhaus 是最先进的。
最后，应用 Zassenhaus 算法对整数进行因式分解。如果您发现它太慢，可以使用 "Lenstra-Lenstra-Lovasz lattice basis reduction algorithm" 进行改进。 http://en.wikipedia.org/wiki/Factorization_of_polynomials#Factoring_univariate_polynomials_over_the_integers
如您所见，这一切都相当复杂，并且依赖于抽象代数中的大量理论。您最好使用与 Sage 相同的库，或者重新实现 Sage 实现，或者甚至只是从您的程序中调用 运行 版本的 Sage 内核。
据此answer on mathoverflow, Sage uses FLINT做因式分解。
FLINT (Fast Library for Number Theory) is a C library in support of computations in number theory. It's also a research project into algorithms in number theory.
因此可以在经过充分测试且稳定的库中查看甚至使用分解算法的实现。