多項式の因数分解
整数係数多項式の各整数で評価した値は有限通りの分解しかないので、十分多くの整数での値から因子の候補となる多項式を(補間公式などにより)構成すれば、因子はこれらの有限個の多項式から見つけられる。
例えば
を考えるとき、これが Z 上で分解するならば、その因子の少なくとも一つは二次以下である。二次多項式を一意に決めるには三点での値が必要であるが、ここでは f(0) = 2, f(1) = 6, f(−1) = 2 を利用することにする。もしここで利用する値のどれかでも 0 に等しくなっていたならば、それはすでに根が見つかった(したがって一次因子が得られた)ことになることに注意せよ。0 に等しいものが無いとすれば、それらの因数は有限個である。いまの場合 2 の因数分解は 1×2, 2×1, (−1)×(−2), (−2)×(−1) の四通りだけであるから、もし二次の整係数因子があったならば、その x = 0 における値は 1, 2, −1, −2 の何れかでなければならない。
上で見たことを踏まえれば、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 たちがそれらの積がこんどは p を法として f と一致するようにできる(ただし、a は p が 2B よりも大きくなるように選ぶものとする)。 この時点で法 p に関して f(x) は(単数を掛ける違いを除いて)2 個の因子を持つ— {f1, ..., fr} の任意の部分集合の各々に対して、その元の総積が f(x) mod p の因子を与える—が、法 p に関する因子が「真の因子」(すなわち、Z[x] における f(x) の因子)に対応するとは限らないことに注意する。
多項式のふたつ以上の因子が互いに一致する場合を考えると、すなわちその多項式はこの因子の平方(平方因子)で割り切れるということになる。一変数多項式の場合だと、そのような因子(多重因子)を与える根は重根と定義される。またこの場合、その多重因子はもとの多項式の導多項式(多変数の場合は、どの変数に関する微分でも)の因子になる。有理数体(あるいはより一般に標数 0 の任意の体)上の一変数多項式の場合、David Yun による無平方分解アルゴリズム(英語版)を用いて、多項式を平方因子を含まない形(而してそれを無平方と言う)に因数分解する方法が実証される。もとの多項式を分解するためには、この各無平方因子の分解を与えれば十分である。したがって、無平方分解はたいていの多項式の因数分解アルゴリズムの緒段となる。
Yun のアルゴリズムは、多変数多項式を多項式環上の一変数多項式と見ることにより、多変数多項式の場合にも拡張することができる。
有限体上の多項式の場合には、Yun のアルゴリズムは多項式の次数が係数体の標数より小さい場合にのみ適用可能である(これは、そうでない場合には非零多項式の導多項式が零多項式となる場合があることによる。例えば p-元体上で冪函数 x の導多項式は常に零である)。それでも、多項式とその導多項式の間のGCD計算があれば無平方分解は得られる(有限体上の多項式の因数分解#無平方分解(英語版)の項を見よ)。