整係数一変数多項式の因数分解

ウィキペディア小見出し辞書

整係数一変数多項式の因数分解

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/16 01:05 UTC 版)

「多項式の因数分解」の記事における「整係数一変数多項式の因数分解」の解説

上で見たことを踏まえれば、f(x) が整係数の一変数多項式のときには、一般性を失うことなくそれが原始的かつ無平方と仮定してよい。すると初めに考えるべきは f の任意の因子 g のすべての係数の絶対値を抑える上界 B を計算することである。そうして m を 2B より大きな整数として、g(x) が m を法として求まったならば、その法 m に関して分かっている g の情報から g が復元できる。 その方法を述べるツァッセンハウス（英語版）のアルゴリズムは以下のようなものである: まず素数 p を f(x) mod p がやはり無平方かつ次数を落とさないように選んで、f(x) mod p を因数分解する。これにより、整係数多項式 f1, …, fr でそれらの積が p を法として f に等しいものが得られる。 次に、ヘンゼル持ち上げ（英語版）を適用して、fi たちがそれらの積がこんどは pa を法として f と一致するようにできる（ただし、a は pa が 2B よりも大きくなるように選ぶものとする）。この時点で法 pa に関して f(x) は（単数を掛ける違いを除いて）2r 個の因子を持つ— {f1, …, fr} の任意の部分集合の各々に対して、その元の総積が f(x) mod pa の因子を与える—が、法 pa に関する因子が「真の因子」（すなわち、ℤ[x] における f(x) の因子）に対応するとは限らないことに注意する。 法 pa に関する各因子に対してそれが真の因子に対応するものかどうかをテストして、対応するものと分かれば（pa が 2B より大きいという仮定のもと）真の因子を計算することになる。この方法では、高々 2r 通りをチェックすれば真の既約因子をすべて見つけることができる（各因子の補因子—掛けて f(x) になるもう一方の因子—についてのチェックは飛ばせるから、実際には 2r−1 通りでよい）。f(x) が可約のときは、既に真の因子であるとわかっている fi についてはチェックを飛ばせるので、調べるべき場合の数はさらに減らすことができる。 ツァッセンハウスのアルゴリズムは各場合のチェックについては手早くできるが、その場合の数が最悪の場合では指数函数的に大きくなってしまう。 有理係数多項式の因数分解を多項式時間で計算できる最初のアルゴリズムは Lenstra, Lenstra & Lovász (1982) が格子基底縮小アルゴリズム（英語版）（"LLLアルゴリズム"）の応用として与えた。簡易版のLLL因数分解アルゴリズムは以下のようなものである: 多項式 f の複素（あるいは p-進）根 α を高精度で計算し、LLL格子基底縮小アルゴリズムを用いて 1, α, α2, … の満たす整係数線型関係式（英語版）（つまり α の満たす整係数多項式関係式）を近似的に求めると、それが（近似でない）真の線型関係式の、したがって f の多項式因子の候補になる。 適切に近似の精度の限界を決めることで、このアルゴリズムが多項式因子か既約性証明の何れかを与えるものであることを保証することができる。この方法は多項式時間であるけれども、格子は高次元のもので、成分数は膨大になり、計算に時間がとられることを考えれば、実用に供されるものではない。 さて、ツァッセンハウスのアルゴリズムの計算量が指数時間となるのは、（f1, …, fr の中から目的に合う部分集合を選び出すという）組合せ問題から来るものであった。ツァッセンハウスと同じやり方ながら組合せ爆発の問題を回避する芸術的因数分解の実装の状態は、組合せ問題をLLLで解決できる格子問題に翻訳する点にある。このやり方の場合、LLL は因数の係数を計算するのではなくて、{0, 1} に r 個の成分をとるベクトル（真の既約因子を与える f1, …, fr の部分集合をエンコードするもの）の計算に用いる。