多項式の因数分解
(Fröhlich & Shepherson 1955) はそのような体で因数分解アルゴリズムの無いようなものの例を与えている。
因数分解アルゴリズムの知られている係数体として、素体(有理数体または素数位数の有限体)およびそれらの有限生成拡大体がある。整係数の場合も扱い易い。クロネッカーの古典的手法は歴史的観点からのみ意義がある。現代的手法は、
無平方分解 (square-free factorization)
有限体上の分解 (factorization over finite fields)
および
多変数多項式から一変数の場合への還元
純超越拡大体(英語版)係数から基礎体上多変数の場合への還元(後述)
代数拡大体係数から基礎体係数への還元(後述)
有理係数から整係数への還元(後述)
整係数から(うまく選んだ素数 p に対する)p-元体係数への還元(後述)
などを組み合わせる形で進められる。
x = −1 における値も同じくである。また同様に、6 の因数分解は 8 通りだから、これらの分解のとり方の組み合わせは 4 × 4 × 8 = 128 通りだが、半分は符号が逆になっただけなので、二次因子となる候補としてチェックすべきものは半分の 64 通りということになる。それ以外のものが f(x) の整係数二次因子を与えることはない。これらを精査すれば
が p(0) = 1, p(1) = 3, p(−1) = 1 を満たすものとして得られて、実際に f(x) を割り切る。 f を p で割れば、別の因子として q ( x ) := x 3 − x + 2 {\textstyle q(x):=x^{3}-x+2} を得るから、因数分解 f = pq を得る。さてさらに再帰的に有理根テストを施して p, q をそれぞれ分解しようと試みれば、これらが Z 上既約であることがわかるから、これで f の既約因子分解
を得た。