多項式の因数分解

数学および計算機代数における多項式の因数分解（いんすうぶんかい、英: factorization of polynomial, polynomial factorization; 多項式の分解）は、与えられた体あるいは整数を係数とする多項式を同じ範囲に係数を持つ既約因子の積として表すことおよびその過程を言う。多項式の分解は計算機代数システムの基本的なツールの一つである。

多項式の因数分解の歴史は、1793年にテオドア・フォン・シューベルトが多項式の分解アルゴリズムを記述したことに始まり、それを1882年に再発見したレオポルト・クロネッカーが多変数の代数体係数多項式に対して拡張している。しかし、このトピックにおける知識の大部分は計算機代数システムの登場する1965年ごろよりも遡らない。この主題に関するサーベイとして Kaltofen (1990) は1982年の文章に 
When the long-known finite step algorithms were first put on computers, they turned out to be highly inefficient. The fact that almost any uni- or multivariate polynomial of degree up to 100 and with coefficients of a moderate size (up to 100 bits) can be factored by modern algorithms in a few minutes of computer time indicates how successfully this problem has been attacked during the past fifteen years. 
（試訳: 古く知られた有限ステップのアルゴリズムを計算機に載せたとき、それらが極めて非効率なものであるとわかった。事実として、100次までの適度な大きさ (100ビット以下) の係数を持つほとんどの一変数あるいは多変数の多項式を、現代アルゴリズムはモノの数分の計算時間で分解できるということが、いかにこの問題がかかる15年の間に成功裏に攻略しつくされたかを指し示している。）
 と記している。
こんにちでは、現代アルゴリズムと計算機により、1000次より上で数千ディジットの係数を持つ場合でも整係数一変数多項式を素早く因数分解することができる。

無平方分解

多項式のふたつ以上の因子が互いに一致する場合を考えると、すなわちその多項式はこの因子の平方（平方因子）で割り切れるということになる。一変数多項式の場合だと、そのような因子（多重因子）を与える根は重根と定義される。またこの場合、その多重因子はもとの多項式の導多項式（多変数の場合は、どの変数に関する微分でも）の因子になる。有理数体（あるいはより一般に標数 0 の任意の体）上の一変数多項式の場合、David Yun による無平方分解アルゴリズムを用いて、多項式を平方因子を含まない形（而してそれを無平方と言う）に因数分解する方法が実証される。もとの多項式を分解するためには、この各無平方因子の分解を与えれば十分である。したがって、無平方分解はたいていの多項式の因数分解アルゴリズムの緒段となる。
Yun のアルゴリズムは、多変数多項式を多項式環上の一変数多項式と見ることにより、多変数多項式の場合にも拡張することができる。
有限体上の多項式の場合には、Yun のアルゴリズムは多項式の次数が係数体の標数より小さい場合にのみ適用可能である（これは、そうでない場合には非零多項式の導多項式が零多項式となる場合があることによる。例えば p-元体上で冪函数 xᵖ の導多項式は常に零である）。それでも、多項式とその導多項式の間のGCD計算があれば無平方分解は得られる（有限体上の多項式の因数分解#無平方分解の項を見よ）。

古典的手法

本節では手計算に便利な教科書的方法について述べる。それらは多項式の分解よりも極めて複雑な一面を持つ自然数の因数分解も利用しているから、計算機に載せるようなものではない。

一次因子の見つけ方

有理係数の範囲での一次因子は何れも有理根テストによって見つけることができる。すなわち、因数分解したい多項式が  であるとき、取りうる任意の一次因子  は、b₁ が aₙ の整数因子かつ b₀ は a₀ の整数因子でなければならない。そのような整数因子すべての組み合わせについて有効か否か確かめて、有効な因子については筆算などして分解を得る。もとの多項式が次数 2 以上の因子を少なくとも二つ含む積であるならば、先に述べた仕方では部分的な分解しか得られないが、そうでなければ完全に一次因子のみの積に分解できることになる。特に、非一次因子がちょうど一つである場合には、それは全ての一次因子を分解し尽くした残りの部分の多項式として取り出せる。三次多項式の場合には、それが完全に因数分解できるならば有理根テストを用いるだけでその分解が決定できる（それは一つの一次因子と二次の既約因子との積であるか、さもなくば三つの一次因子の積である）ことは注目に値する。

クロネッカーの方法

整係数多項式は整係数多項式因子に分解されなければならないこと、および整係数多項式を整数において評価したものは整数でなければならないことから、多項式のそれら整数値の分解は有限通りに限られ、取りうる多項式因子も有限通りだけが見つけられる。
例えば 
 を考えるとき、これが ℤ 上で分解するならば、その因子の少なくとも一つは二次以下である。二次多項式を一意に決めるには三点での値が必要であるが、ここでは 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 の何れかでなければならない。x = −1 における値も同じくである。また同様に、6 の因数分解は 8 通りだから、これらの分解のとり方の組み合わせは 4 × 4 × 8 = 128 通りだが、半分は符号が逆になっただけなので、二次因子となる候補としてチェックすべきものは半分の 64 通りということになる。それ以外のものが f(x) の整係数二次因子を与えることはない。これらを精査すれば 
 が p(0) = 1, p(1) = 3, p(−1) = 1 を満たすものとして得られて、実際に f(x) を割り切る。
f を p で割れば、別の因子として  を得るから、因数分解 f = pq を得る。さてさらに再帰的に有理根テストを施して p, q をそれぞれ分解しようと試みれば、これらが ℤ 上既約であることがわかるから、これで f の既約因子分解 
 を得た。

代数体係数の場合: Trager の方法

体 K が代数体（ℚ の有限次拡大体）であるときの多項式 p(x) ∈ K[x] も因数分解することができる。無平方分解して、多項式は無平方であると仮定してよい。ℚ 上の線型環として L := K[x]/(p(x)) と陽に書いて、無作為に α ∈ L をとれば、原始元定理により、高確率で α は L を ℚ 上生成する。生成することが確認できたならば、α の ℚ 上の最小多項式 q(y) ∈ ℚ[y] を計算して、それを ℚ[y] 上で
 と因数分解することで、
 と決定できて（p は無平方であるから、L が被約環となることに注意）、α は右辺の元 (y, …, y)（全ての成分が y）に対応する。これが体の直積としての L の唯一の分解であることに注意する。したがってこの分解は 
 と同じものである（ここに p = ∏m
i=1 pᵢ は p の K[x] における既約分解とする）。x ∈ L および K の生成元を α の多項式として書けば、x および K の ℚ[y]/(qᵢ(y)) = K[x]/(pᵢ(x)) の直積因子の中への埋め込みが決定できる。この環における x の最小多項式を求めることにより、pᵢ が計算できて、したがって p が K 上で既約分解される。