ベルレーカンプ–ザーセンハウスアルゴリズム - 百科事典

数学において、特に計算代数学において、Berlekamp-Zassenhausアルゴリズムは、エルウィン・ベルレカンプとハンス・ザーゼナウスに名付けられた整数上での多項式の因数分解アルゴリズムです。ガウスのリーマの結果、これにより、有理数上での問題も解決することになります。

このアルゴリズムは、ヘンスルのリーマを用いて、素数pに対するモディuで解が見つかるように、適切な有限体上での因数分解を探し始めます。これ以降、右の因数はこれらの集合の一部として見つけられます。

このアルゴリズムの最悪のケースは、因数の数に指数関数的に依存します。

Van Hoeij（2002年）は、LLLアルゴリズムを用いてこのアルゴリズムを改善し、モディpの因数の適切な集合を選ぶために必要な時間を大幅に短縮しました。

参考資料
Berlekamp, E. R.（1967）「有限体上での多項式の因数分解」Bell System Technical Journal, 46（8）: 1853–1859, doi:10.1002/j.1538-7305.1967.tb03174.x, MR 0219231。
Berlekamp, E. R.（1970）「大きな有限体上での多項式の因数分解」Mathematics of Computation, 24（111）: 713–735, doi:10.2307/2004849, JSTOR 2004849, MR 0276200。
Cantor, David G.; Zassenhaus, Hans（1981）「有限体上での多項式の因数分解のための新しいアルゴリズム」Mathematics of Computation, 36（154）: 587–592, doi:10.2307/2007663, JSTOR 2007663, MR 0606517。
Geddes, K. O.; Czapor, S. R.; Labahn, G.（1992）「コンピュータ代数のためのアルゴリズム」Boston, MA: Kluwer Academic Publishers, Bibcode:1992afca.book.....G, doi:10.1007/b102438, ISBN 0-7923-9259-0, MR 1256483。
Van Hoeij, Mark（2002）「多項式の因数分解とバックパック問題」Journal of Number Theory, 95（2）: 167–189, doi:10.1016/S0022-314X(01)92763-5, MR 1924096。
Zassenhaus, Hans（1969）「ヘンスルの因数分解法．I」Journal of Number Theory, 1（3）: 291–311, Bibcode:1969JNT.....1..291Z, doi:10.1016/0022-314X(69)90047-X, MR 0242793。

外部リンク
Domazet, Haris. "Berlekamp-Zassenhaus Algorithm". MathWorld.