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

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

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

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

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