主题
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 贡献

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 上被引用

Berlekamp-Zassenhaus 算法

引用为

Domazet, Haris. “Berlekamp-Zassenhaus 算法。” 来自 MathWorld——Wolfram Web 资源，由 Eric W. Weisstein 创建。 https://mathworld.net.cn/Berlekamp-ZassenhausAlgorithm.html

主题分类