多項式の因数分解

数学および計算機代数における多項式の因数分解（いんすうぶんかい、; 多項式の分解）は、与えられた体あるいは整数を係数とする多項式を同じ範囲に係数を持つ既約因子の積として表すことおよびその過程を言う。多項式の分解は計算機代数システムの基本的なツールの一つである。
多項式の因数分解の歴史は、1793年にが多項式の分解アルゴリズムを記述したことに始まり、それを1882年に再発見したレオポルト・クロネッカーが多変数の代数体係数多項式に対して拡張している。しかし、このトピックにおける知識の大部分は計算機代数システムの登場する1965年ごろよりも遡らない。この主題に関するサーベイとして は1982年の文章に と記している。
こんにちでは、現代アルゴリズムと計算機により、1000次より上で数千ディジットの係数を持つ場合でも整係数一変数多項式を素早く因数分解することができる。
問題の定式化について.
整係数あるいは体上の多項式環はUFDである。その意味するところは、これら環の任意の元が定数と既約多項式（定数でない二つの多項式の積に書くことのできない多項式）の積になっているということ、さらにはその分解が可逆な定数を掛ける違いを除いて一意となることである。
この因数分解は係数体の種類に依存する。例えば、代数学の基本定理（複素係数の任意の多項式が複素根を持つこと）から、任意の整係数多項式を複素数体 上の一次因子の積に完全に分解することができることが従う。同様に、実数体 上では既約因子の次数は であり、対して有理数体 上では任意の次数の既約多項式が存在する。
多項式の因数分解問題は、そのすべての元を計算機で表現できる計算可能数体 (computable field) を係数とし、算術的演算を用いたアルゴリズムが存在する場合にのみ意味をなす。 はそのような体で因数分解アルゴリズムの無いようなものの例を与えている。
因数分解アルゴリズムの知られている係数体として、素体（有理数体または素数位数の有限体）およびそれらの有限生成拡大体がある。整係数の場合も扱い易い。クロネッカーの古典的手法は歴史的観点からのみ意義がある。現代的手法は、
および
などを組み合わせる形で進められる。
内容–原始成分分解.
本節では、有理数体 上での因数分解は整数環 上での因数分解と本質的に同じ問題であることを示す。
カール・フリードリヒ・ガウスは二つの原始多項式の積がふたたび原始的であること（）を示した。これにより「原始多項式が有理数体上既約であるための必要十分条件は、整数環上で既約であること」が従う。これはつまり、有理係数多項式の有理数体上での因数分解が、その原始成分の整数環上での因数分解と同じことであることをも意味する。他方、整係数多項式の整数環上での因数分解は、その原始成分の分解と内容の素因数分解とを掛けることで与えられる。
言い方を変えれば、整数のGCD計算によって有理係数多項式の因数分解は整係数原始多項式の因数分解に帰着され、また整数環上での因数分解は整数の因数分解と原始多項式の因数分解に帰着することができるようになるということである。
さてここまでに述べたことは、 を体 上の多項式環で、および を の有理函数体でそれぞれ置き換えて（ただし置き換え後の両者の不定元は共通とする）、「符号の違いを除いて」という代わりに「 の単元を掛ける違いを除いて」とすれば、すべてそのまま成り立つ。この場合、 の純超越拡大体上での因数分解が 上の多変数多項式の因数分解に帰着される。
無平方分解.
多項式のふたつ以上の因子が互いに一致する場合を考えると、すなわちその多項式はこの因子の平方（平方因子）で割り切れるということになる。一変数多項式の場合だと、そのような因子（多重因子）を与える根は重根と定義される。またこの場合、その多重因子はもとの多項式の導多項式（多変数の場合は、どの変数に関する微分でも）の因子になる。有理数体（あるいはより一般に標数 の任意の体）上の一変数多項式の場合、David Yun によるを用いて、多項式を平方因子を含まない形（而してそれを無平方と言う）に因数分解する方法が実証される。もとの多項式を分解するためには、この各無平方因子の分解を与えれば十分である。したがって、無平方分解はたいていの多項式の因数分解アルゴリズムの緒段となる。
Yun のアルゴリズムは、多変数多項式を多項式環上の一変数多項式と見ることにより、多変数多項式の場合にも拡張することができる。
有限体上の多項式の場合には、Yun のアルゴリズムは多項式の次数が係数体の標数より小さい場合にのみ適用可能である（これは、そうでない場合には非零多項式の導多項式が零多項式となる場合があることによる。例えば -元体上で冪函数 の導多項式は常に零である）。それでも、多項式とその導多項式の間のGCD計算があれば無平方分解は得られる（の項を見よ）。
古典的手法.
本節では手計算に便利な教科書的方法について述べる。それらは多項式の分解よりも極めて複雑な一面を持つ自然数の因数分解も利用しているから、計算機に載せるようなものではない。
一次因子の見つけ方.
有理係数の範囲での一次因子は何れも有理根テストによって見つけることができる。すなわち、因数分解したい多項式が formula_3 であるとき、取りうる任意の一次因子 formula_4 は、 が の整数因子かつ は の整数因子でなければならない。そのような整数因子すべての組み合わせについて有効か否か確かめて、有効な因子についてはなどして分解を得る。もとの多項式が次数 以上の因子を少なくとも二つ含む積であるならば、先に述べた仕方では部分的な分解しか得られないが、そうでなければ完全に一次因子のみの積に分解できることになる。特に、非一次因子がちょうど一つである場合には、それは全ての一次因子を分解し尽くした残りの部分の多項式として取り出せる。三次多項式の場合には、それが完全に因数分解できるならば有理根テストを用いるだけでその分解が決定できる（それは一つの一次因子と二次の既約因子との積であるか、さもなくば三つの一次因子の積である）ことは注目に値する。
クロネッカーの方法.
整数係数多項式の各整数で評価した値は有限通りの分解しかないので、十分多くの整数での値から因子の候補となる多項式を（補間公式などにより）構成すれば、因子はこれらの有限個の多項式から見つけられる。
例えば formula_5 を考えるとき、これが 上で分解するならば、その因子の少なくとも一つは二次以下である。二次多項式を一意に決めるには三点での値が必要であるが、ここでは , , を利用することにする。もしここで利用する値のどれかでも に等しくなっていたならば、それはすでに根が見つかった（したがって一次因子が得られた）ことになることに注意せよ。 に等しいものが無いとすれば、それらの因数は有限個である。いまの場合 の因数分解は の四通りだけであるから、もし二次の整係数因子があったならば、その における値は の何れかでなければならない。 における値も同じくである。また同様に、 の因数分解は 通りだから、これらの分解のとり方の組み合わせは 通りだが、半分は符号が逆になっただけなので、二次因子となる候補としてチェックすべきものは半分の 64 通りということになる。それ以外のものが の整係数二次因子を与えることはない。これらを精査すれば formula_6 が , , を満たすものとして得られて、実際に を割り切る。
 を で割れば、別の因子として formula_7 を得るから、因数分解 を得る。さてさらに再帰的に有理根テストを施して をそれぞれ分解しようと試みれば、これらが 上既約であることがわかるから、これで の既約因子分解 formula_8 を得た。
現代的手法.
整係数一変数多項式の因数分解.
上で見たことを踏まえれば、 が整係数の一変数多項式のときには、一般性を失うことなくそれが原始的かつ無平方と仮定してよい。すると初めに考えるべきは の任意の因子 のすべての係数の絶対値を抑える上界 を計算することである。そうして を より大きな整数として、 が を法として求まったならば、その法 に関して分かっている の情報から が復元できる。
その方法を述べるのアルゴリズムは以下のようなものである:
ツァッセンハウスのアルゴリズムは各場合のチェックについては手早くできるが、その場合の数が最悪の場合では指数函数的に大きくなってしまう。
有理係数多項式の因数分解を多項式時間で計算できる最初のアルゴリズムは が（"LLLアルゴリズム"）の応用として与えた。簡易版のLLL因数分解アルゴリズムは以下のようなものである: 
適切に近似の精度の限界を決めることで、このアルゴリズムが多項式因子か既約性証明の何れかを与えるものであることを保証することができる。この方法は多項式時間であるけれども、格子は高次元のもので、成分数は膨大になり、計算に時間がとられることを考えれば、実用に供されるものではない。
さて、ツァッセンハウスのアルゴリズムの計算量が指数時間となるのは、（ の中から目的に合う部分集合を選び出すという）組合せ問題から来るものであった。ツァッセンハウスと同じやり方ながら組合せ爆発の問題を回避する芸術的因数分解の実装の状態は、組合せ問題をLLLで解決できる格子問題に翻訳する点にある。このやり方の場合、LLL は因数の係数を計算するのではなくて、 に 個の成分をとるベクトル（真の既約因子を与える の部分集合をエンコードするもの）の計算に用いる。
代数体係数の場合: Trager の方法.
体 が代数体（ の有限次拡大体）であるときの多項式 も因数分解することができる。無平方分解して、多項式は無平方であると仮定してよい。 上の線型環として と陽に書いて、無作為に をとれば、原始元定理により、高確率で は を 上生成する。生成することが確認できたならば、 の 上の最小多項式 を計算して、それを 上でformula_9 と因数分解することで、formula_10 と決定できて（ は無平方であるから、 が被約環となることに注意）、 は右辺の元 （全ての成分が ）に対応する。これが体の直積としての の唯一の分解であることに注意する。したがってこの分解は formula_11 と同じものである（ここに は の における既約分解とする）。 および の生成元を の多項式として書けば、 および の の直積因子の中への埋め込みが決定できる。この環における の最小多項式を求めることにより、 が計算できて、したがって が 上で既約分解される。