主題
Search

Berlekamp-Zassenhaus 演算法

一種可用於分解整數上的多項式 f 的演算法。該演算法首先透過 Berlekamp 方法將 f 對合適的素數 p 取模進行分解，然後使用 Hensel 提升將其提升為模 p^2 的分解，然後是 p^4，然後是 p^8，...，直到某個界限 p^n。這具有二次收斂性。在此過程之後，選擇這些因子的正確子集，以便獲得具有整數係數的因子。此過程的最壞情況複雜度在因子數量上呈指數級增長，因為可能需要檢查指數級的組合。透過取 f 在 Z[x] 中的不可約多項式來獲得壞例子，它對每個模數 p 都有許多不同的因子。

van Hoeij (2002) 透過提供一種解決組合問題的更好方法改進了該演算法。他的方法使用格縮減（更具體地說是 LLL 演算法），並且它大大減少了選擇模 p^n 因子的正確子集所需的時間。

另請參閱

有限域, 多項式分解

此條目由 Haris Domazet 貢獻

使用 探索

參考文獻

Berlekamp, E. R. "Factoring Polynomials over Finite Fields." Bell System Technical J. 46, 1853-1859, 1967.Berlekamp, E. R. "Factoring Polynomials over Finite Fields." Math. Comput. 24, 713-735, 1970.Cantor, D. G. 和 Zassenhaus, H. "A New Algorithm for Factoring Polynomials over Finite Fields." Math. Comput. 36, 587-592, 1981.Geddes, K. O.; Czapor, S. R.; 和 Labahn, G. 計算機代數演算法。 阿姆斯特丹，荷蘭：Kluwer，1992 年。van Hoeij, M. "Factoring Polynomials and the Knapsack Problem." J. Number Th. 95, 167-189, 2002.Zassenhaus, H. "On Hensel Factorization, I." J. Number Th. 1, 291-311, 1969.

在 上被引用

Berlekamp-Zassenhaus 演算法

引用為

Domazet, Haris. “Berlekamp-Zassenhaus 演算法。” 來自 —— 資源，由 Eric W. Weisstein 建立。 https://mathworld.tw/Berlekamp-ZassenhausAlgorithm.html

主題分類