具有整數係數的多項式的快速因式分解

我想在整數環上快速分解多項式（原始多項式具有整數係數，所有因子都有整數係數）。具有整數係數的多項式的快速因式分解

比如我想分解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

具有整數係數的多項式的快速因式分解

回答

相關問題