多項式の因数分解

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

多項式の因数分解の歴史は、1793年にテオドール・フォン・シューベルトが多項式の分解アルゴリズムを記述したことに始まり、それを1882年に再発見したレオポルト・クロネッカーが多変数の代数体係数多項式に対して拡張している。しかし、このトピックにおける知識の大部分は計算機代数システムの登場する1965年ごろよりも遡らない。この主題に関するサーベイとして Kaltofen は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  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.

}} と記している。

こんにちでは、現代アルゴリズムと計算機により、1000次より上で数千ディジットの係数を持つ場合でも整係数一変数多項式を素早く因数分解することができる。

1. 問題の定式化について
-------------

整係数あるいは体上の多項式環はUFDである。その意味するところは、これら環の任意の元が定数と既約多項式の積になっているということ、さらにはその分解が可逆な定数を掛ける違いを除いて一意となることである。

この因数分解は係数体の種類に依存する。例えば、代数学の基本定理から、任意の整係数多項式を複素数体 ℂ}} 上の一次因子の積に完全に分解することができることが従う。同様に、実数体 ℝ}} 上では既約因子の次数は高々 math であり、対して有理数体 ℚ}} 上では任意の次数の既約多項式が存在する。

多項式の因数分解問題は、そのすべての元を計算機で表現できる計算可能数体  を係数とし、算術的演算を用いたアルゴリズムが存在する場合にのみ意味をなす。Fröhlich はそのような体で因数分解アルゴリズムの無いようなものの例を与えている。

因数分解アルゴリズムの知られている係数体として、素体およびそれらの有限生成拡大体がある。整係数の場合も扱い易い。クロネッカーの古典的手法は歴史的観点からのみ意義がある。現代的手法は、

無平方分解 
有限体上の分解 および

多変数多項式から一変数の場合への還元
純超越拡大体係数から基礎体上多変数の場合への還元
代数拡大体係数から基礎体係数への還元
有理係数から整係数への還元
整係数からp}}-元体係数への還元などを組み合わせる形で進められる。

2. 内容–原始成分分解
------------

本節では、有理数体 ℚ}} 上での因数分解は整数環 ℤ}} 上での因数分解と本質的に同じ問題であることを示す。

整係数多項式 //p// ∈ ℤbracket の内容 "cont}}" はp}} のすべての係数の最大公約数を言い、p}} の原始成分 1=prim-part coloneqq}} //p///cont}} は整係数の原始多項式である。これらによって p}} は原始多項式の整数倍という形への分解が定義され、内容の符号の違いを除いて一意に定まる。通常は、内容の符号は原始成分の最高次係数が正となるようにとる。
任意の有理係数多項式 q}} は の形に書き直せる。このとき q}} の内容は で、また q}} の原始成分は p}} のそれで、それぞれ定義する。整係数多項式の場合と同様に、この場合も、有理係数多項式を有理数と整係数原始多項式の積への分解が、符号のとり方を除いて一意に定義される。カール・フリードリヒ・ガウスは二つの原始多項式の積がふたたび原始的であることを示した。これにより「原始多項式が有理数体上既約であるための必要十分条件は、整数環上で既約であること」が従う。これはつまり、有理係数多項式の有理数体上での因数分解が、その原始成分の整数環上での因数分解と同じことであることをも意味する。他方、整係数多項式の整数環上での因数分解は、その原始成分の分解と内容の素因数分解とを掛けることで与えられる。

言い方を変えれば、整数のGCD計算によって有理係数多項式の因数分解は整係数原始多項式の因数分解に帰着され、また整数環上での因数分解は整数の因数分解と原始多項式の因数分解に帰着することができるようになるということである。

さてここまでに述べたことは、ℤ}} を体 F}} 上の多項式環で、および ℚ}} を F}} の有理函数体でそれぞれ置き換えて、「符号の違いを除いて」という代わりに「F}} の単元を掛ける違いを除いて」とすれば、すべてそのまま成り立つ。この場合、F}} の純超越拡大体上での因数分解が F}} 上の多変数多項式の因数分解に帰着される。

3. 無平方分解
--------

多項式のふたつ以上の因子が互いに一致する場合を考えると、すなわちその多項式はこの因子の平方で割り切れるということになる。一変数多項式の場合だと、そのような因子を与える根は重根と定義される。またこの場合、その多重因子はもとの多項式の導多項式の因子になる。有理数体上の一変数多項式の場合、David Yun による無平方多項式#Yunのアルゴリズムを用いて、多項式を平方因子を含まない形に因数分解する方法が実証される。もとの多項式を分解するためには、この各無平方因子の分解を与えれば十分である。したがって、無平方分解はたいていの多項式の因数分解アルゴリズムの緒段となる。

Yun のアルゴリズムは、多変数多項式を多項式環上の一変数多項式と見ることにより、多変数多項式の場合にも拡張することができる。

有限体上の多項式の場合には、Yun のアルゴリズムは多項式の次数が係数体の標数より小さい場合にのみ適用可能である。それでも、多項式とその導多項式の間のGCD計算があれば無平方分解は得られる。

4. 古典的手法
--------

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

4.1. 一次因子の見つけ方
--------------

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

4.2. クロネッカーの方法
--------------

整数係数多項式の各整数で評価した値は有限通りの分解しかないので、十分多くの整数での値から因子の候補となる多項式を構成すれば、因子はこれらの有限個の多項式から見つけられる。

例えば を考えるとき、これが ℤ}} 上で分解するならば、その因子の少なくとも一つは二次以下である。二次多項式を一意に決めるには三点での値が必要であるが、ここでは 1=//f// = 2}}, 1=//f// = 6}}, 1=//f// = 2}} を利用することにする。もしここで利用する値のどれかでも 0}} に等しくなっていたならば、それはすでに根が見つかったことになることに注意せよ。0}} に等しいものが無いとすれば、それらの因数は有限個である。いまの場合 2}} の因数分解は 1×2, 2×1, ×, ×}} の四通りだけであるから、もし二次の整係数因子があったならば、その 1=//x// = 0}} における値は 1, 2, −1, −2}} の何れかでなければならない。1=//x// = −1}} における値も同じくである。また同様に、6}} の因数分解は 8}} 通りだから、これらの分解のとり方の組み合わせは 1=4 × 4 × 8 = 128}} 通りだが、半分は符号が逆になっただけなので、二次因子となる候補としてチェックすべきものは半分の 64 通りということになる。それ以外のものが //f//}} の整係数二次因子を与えることはない。これらを精査すれば が 1=//p// = 1}}, 1=//p// = 3}}, 1=//p// = 1}} を満たすものとして得られて、実際に //f//}} を割り切る。

f}} を p}} で割れば、別の因子として を得るから、因数分解 1=//f// = //pq//}} を得る。さてさらに再帰的に有理根テストを施して p, q}} をそれぞれ分解しようと試みれば、これらが ℤ}} 上既約であることがわかるから、これで f}} の既約因子分解 を得たvan der Waerden。

5. 現代的手法
--------

5.1. 有限体上の因数分解
--------------

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

上で見たことを踏まえれば、//f//}} が整係数の一変数多項式のときには、一般性を失うことなくそれが原始的かつ無平方と仮定してよい。すると初めに考えるべきは f}} の任意の因子 g}} のすべての係数の絶対値を抑える上界 B}} を計算することである。そうして m}} を 2//B//}} より大きな整数として、//g//}} が m}} を法として求まったならば、その法 m}} に関して分かっている g}} の情報から g}} が復元できる。

その方法を述べるハンス・ユリウス・ツァッセンハウスのアルゴリズムは以下のようなものである:

まず素数 p}} を //f// mod //p//}} がやはり無平方かつ次数を落とさないように選んで、//f// mod //p//}} を因数分解する。これにより、整係数多項式 //f//sub でそれらの積が p}} を法として f}} に等しいものが得られる。
次に、ヘンゼル持ち上げを適用して、fsub たちがそれらの積がこんどは pexp を法として f}} と一致するようにできる。
この時点で法 pexp に関して //f//}} は2exp 個の因子を持つ— mset の任意の部分集合の各々に対して、その元の総積が //f// mod //pexp の因子を与える—が、法 pexp に関する因子が「真の因子」に対応するとは限らないことに注意する。//
法 pexp に関する各因子に対してそれが真の因子に対応するものかどうかをテストして、対応するものと分かれば真の因子を計算することになる。
この方法では、高々 2exp 通りをチェックすれば真の既約因子をすべて見つけることができる。//f//}} が可約のときは、既に真の因子であるとわかっている fsub についてはチェックを飛ばせるので、調べるべき場合の数はさらに減らすことができる。ツァッセンハウスのアルゴリズムは各場合のチェックについては手早くできるが、その場合の数が最悪の場合では指数函数的に大きくなってしまう。

有理係数多項式の因数分解を多項式時間で計算できる最初のアルゴリズムは Lenstra がレンストラ–レンストラ–ロヴァッツの格子基底縮小アルゴリズムの応用として与えた。簡易版のLLL因数分解アルゴリズムは以下のようなものである:

多項式 f}} の複素根 α}} を高精度で計算し、LLL格子基底縮小アルゴリズムを用いて 1, //α//, //α//exp の満たす整数関係アルゴリズムを近似的に求めると、それが真の線型関係式の、したがって f}} の多項式因子の候補になる。適切に近似の精度の限界を決めることで、このアルゴリズムが多項式因子か既約性証明の何れかを与えるものであることを保証することができる。この方法は多項式時間であるけれども、格子は高次元のもので、成分数は膨大になり、計算に時間がとられることを考えれば、実用に供されるものではない。

さて、ツァッセンハウスのアルゴリズムの計算量が指数時間となるのは、組合せ問題から来るものであった。ツァッセンハウスと同じやり方ながら組合せ爆発の問題を回避する芸術的因数分解の実装の状態は、組合せ問題をLLLで解決できる格子問題に翻訳する点にある。このやり方の場合、LLL は因数の係数を計算するのではなくて、mset に r}} 個の成分をとるベクトルの計算に用いる。

5.3. 代数体係数の場合: Trager の方法
-------------------------

体 K}} が代数体であるときの多項式 //p// ∈ //K//bracket も因数分解することができる。無平方分解して、多項式は無平方であると仮定してよい。ℚ}} 上の線型環として //L// coloneqq}} //K//bracket と陽に書いて、無作為に //α// ∈ //L//}} をとれば、原始元定理により、高確率で α}} は L}} を ℚ}} 上生成する。生成することが確認できたならば、α}} の ℚ}} 上の最小多項式 //q// ∈ ℚbracket を計算して、それを ℚbracket 上で と因数分解することで、 と決定できて、α}} は右辺の元 }}に対応する。これが体の直積としての L}} の唯一の分解であることに注意する。したがってこの分解は と同じものである。//x// ∈ //L//}} および K}} の生成元を α}} の多項式として書けば、x}} および K}} の 1=ℚbracket の直積因子の中への埋め込みが決定できる。この環における x}} の最小多項式を求めることにより、psub が計算できて、したがって p}} が K}} 上で既約分解される。

6. 注
----

6.1. 注釈
-------

6.2. 出典
-------

7. 参考文献
-------

title=Quantitative Estimates for Polynomials in One or Several Variables: From Analysis and Number Theory to Symbolic and Massively Parallel Computation

8. 関連文献
-------

9. 外部リンク
--------

10. 関連項目
--------

因数分解#多項式の因数分解