多項式の因数分解

提供: testwiki
ナビゲーションに移動 検索に移動
テオドール・フォン・シューベルト

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

多項式の因数分解の歴史は、1793年にテンプレート:Ill2が多項式の分解アルゴリズムを記述したこと[1]に始まり、それを1882年に再発見したレオポルト・クロネッカーが多変数の代数体係数多項式に対して拡張している。しかし、このトピックにおける知識の大部分は計算機代数システムの登場する1965年ごろよりも遡らない。この主題に関するサーベイとして テンプレート:Harvtxt は1982年の文章に テンプレート:Quotation と記している。

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

問題の定式化について

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

この因数分解は係数体の種類に依存する。例えば、代数学の基本定理（複素係数の任意の多項式が複素根を持つこと）から、任意の整係数多項式を複素数体 テンプレート:Mathbf 上の一次因子の積に完全に分解することができることが従う。同様に、実数体 テンプレート:Mathbf 上では既約因子の次数はテンプレート:Nowrap であり、対して有理数体 テンプレート:Mathbf 上では任意の次数の既約多項式が存在する。

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

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

  • 無平方分解 (square-free factorization)
  • 有限体上の分解 (factorization over finite fields)

および

などを組み合わせる形で進められる。

内容–原始成分分解

テンプレート:See also 本節では、有理数体 テンプレート:Mathbf 上での因数分解は整数環 テンプレート:Mathbf 上での因数分解と本質的に同じ問題であることを示す。テンプレート:Efn

カール・フリードリヒ・ガウスは二つの原始多項式の積がふたたび原始的であること（テンプレート:Ill2）を示した。これにより「原始多項式が有理数体上既約であるための必要十分条件は、整数環上で既約であること」が従う。これはつまり、有理係数多項式の有理数体上での因数分解が、その原始成分の整数環上での因数分解と同じことであることをも意味する。他方、整係数多項式の整数環上での因数分解は、その原始成分の分解と内容の素因数分解とを掛けることで与えられる。

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

さてここまでに述べたことは、テンプレート:Mathbf を体 テンプレート:Mvar 上の多項式環で、および テンプレート:Mathbf を テンプレート:Mvar の有理函数体でそれぞれ置き換えて（ただし置き換え後の両者の不定元は共通とする）、「符号の違いを除いて」という代わりに「テンプレート:Mvar の単元を掛ける違いを除いて」とすれば、すべてそのまま成り立つ。この場合、テンプレート:Mvar の純超越拡大体上での因数分解が テンプレート:Mvar 上の多変数多項式の因数分解に帰着される。

無平方分解

テンプレート:Main 多項式のふたつ以上の因子が互いに一致する場合を考えると、すなわちその多項式はこの因子の平方（平方因子）で割り切れるということになる。一変数多項式の場合だと、そのような因子（多重因子）を与える根は重根と定義される。またこの場合、その多重因子はもとの多項式の導多項式（多変数の場合は、どの変数に関する微分でも）の因子になる。有理数体（あるいはより一般に標数 テンプレート:Math の任意の体）上の一変数多項式の場合、David Yun によるテンプレート:Ill2を用いて、多項式を平方因子を含まない形（而してそれを無平方と言う）に因数分解する方法が実証される。もとの多項式を分解するためには、この各無平方因子の分解を与えれば十分である。したがって、無平方分解はたいていの多項式の因数分解アルゴリズムの緒段となる。

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

有限体上の多項式の場合には、Yun のアルゴリズムは多項式の次数が係数体の標数より小さい場合にのみ適用可能である（これは、そうでない場合には非零多項式の導多項式が零多項式となる場合があることによる。例えば テンプレート:Mvar-元体上で冪函数 テンプレート:Mvar の導多項式は常に零である）。それでも、多項式とその導多項式の間のGCD計算があれば無平方分解は得られる（テンプレート:Ill2の項を見よ）。

古典的手法

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

一次因子の見つけ方

有理係数の範囲での一次因子は何れも有理根テストによって見つけることができる。すなわち、因数分解したい多項式が anxn+an−1xn−1+⋯+a1x+a0 であるとき、取りうる任意の一次因子 b1x−b0 は、テンプレート:Math が テンプレート:Mvar の整数因子かつ テンプレート:Math は テンプレート:Math の整数因子でなければならない。そのような整数因子すべての組み合わせについて有効か否か確かめて、有効な因子についてはテンプレート:Ill2などして分解を得る。もとの多項式が次数 テンプレート:Math 以上の因子を少なくとも二つ含む積であるならば、先に述べた仕方では部分的な分解しか得られないが、そうでなければ完全に一次因子のみの積に分解できることになる。特に、非一次因子がちょうど一つである場合には、それは全ての一次因子を分解し尽くした残りの部分の多項式として取り出せる。三次多項式の場合には、それが完全に因数分解できるならば有理根テストを用いるだけでその分解が決定できる（それは一つの一次因子と二次の既約因子との積であるか、さもなくば三つの一次因子の積である）ことは注目に値する。

クロネッカーの方法

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

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

テンプレート:Mvar を テンプレート:Mvar で割れば、別の因子として q(x):=x3−x+2 を得るから、因数分解 テンプレート:Math を得る。さてさらに再帰的に有理根テストを施して テンプレート:Mvar をそれぞれ分解しようと試みれば、これらが テンプレート:Mathbf 上既約であることがわかるから、これで テンプレート:Mvar の既約因子分解 f(x)=p(x)q(x)=(x2+x+1)(x3−x+2) を得たテンプレート:Sfn。

現代的手法

有限体上の因数分解

テンプレート:Main

ハンス・ユリウス・ツァッセンハウス

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

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

その方法を述べるテンプレート:Ill2のアルゴリズムは以下のようなものである:

  1. まず素数 テンプレート:Mvar を テンプレート:Math がやはり無平方かつ次数を落とさないように選んで、テンプレート:Math を因数分解する。これにより、整係数多項式 テンプレート:Math でそれらの積が テンプレート:Mvar を法として テンプレート:Mvar に等しいものが得られる。
  2. 次に、ヘンゼル持ち上げを適用して、テンプレート:Mvar たちがそれらの積がこんどは テンプレート:Mvar を法として テンプレート:Mvar と一致するようにできる（ただし、テンプレート:Mvar は テンプレート:Mvar が テンプレート:Math よりも大きくなるように選ぶものとする）。
  3. 法 テンプレート:Mvar に関する各因子に対してそれが真の因子に対応するものかどうかをテストして、対応するものと分かれば（テンプレート:Mvar が テンプレート:Math より大きいという仮定のもと）真の因子を計算することになる。
    • この方法では、高々 テンプレート:Math 通りをチェックすれば真の既約因子をすべて見つけることができる（各因子の補因子—掛けて f(x) になるもう一方の因子—についてのチェックは飛ばせるから、実際には テンプレート:Math 通りでよい）。テンプレート:Math が可約のときは、既に真の因子であるとわかっている テンプレート:Mvar についてはチェックを飛ばせるので、調べるべき場合の数はさらに減らすことができる。

ツァッセンハウスのアルゴリズムは各場合のチェックについては手早くできるが、その場合の数が最悪の場合では指数函数的に大きくなってしまう。

有理係数多項式の因数分解を多項式時間で計算できる最初のアルゴリズムは テンプレート:Harvtxt がテンプレート:Ill2（"LLLアルゴリズム"）の応用として与えた。簡易版のLLL因数分解アルゴリズムは以下のようなものである:

多項式 テンプレート:Mvar の複素（あるいは テンプレート:Mvar-進）根 テンプレート:Mvar を高精度で計算し、LLL格子基底縮小アルゴリズムを用いて テンプレート:Math2 の満たすテンプレート:Ill2（つまり テンプレート:Mvar の満たす整係数多項式関係式）を近似的に求めると、それが（近似でない）真の線型関係式の、したがって テンプレート:Mvar の多項式因子の候補になる。

適切に近似の精度の限界を決めることで、このアルゴリズムが多項式因子か既約性証明の何れかを与えるものであることを保証することができる。この方法は多項式時間であるけれども、格子は高次元のもので、成分数は膨大になり、計算に時間がとられることを考えれば、実用に供されるものではない。

さて、ツァッセンハウスのアルゴリズムの計算量が指数時間となるのは、（テンプレート:Math の中から目的に合う部分集合を選び出すという）組合せ問題から来るものであった。ツァッセンハウスと同じやり方ながら組合せ爆発の問題を回避する芸術的因数分解の実装の状態は、組合せ問題をLLLで解決できる格子問題に翻訳する点にある[3]。このやり方の場合、LLL は因数の係数を計算するのではなくて、テンプレート:Math に テンプレート:Mvar 個の成分をとるベクトル（真の既約因子を与える テンプレート:Math の部分集合をエンコードするもの）の計算に用いる。

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

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

注

テンプレート:脚注ヘルプ

注釈

テンプレート:Notelist

出典

テンプレート:Reflist

参考文献

テンプレート:Reflist

関連文献

外部リンク

関連項目

テンプレート:多項式

  1. ↑ FT Schubert: De Inventione Divisorum Nova Acta Academiae Scientiarum Petropolitanae v.11, p. 172-182(1793)
  2. ↑ An example of degree 2401, taking 7.35 seconds, is found in Section 4 in: Hart, van Hoeij, Novocin: Practical Polynomial Factoring in Polynomial Time ISSAC'2011 Proceedings, p. 163-170 (2011).
  3. ↑ M. van Hoeij: Factoring polynomials and the knapsack problem. Journal of Number Theory, 95, 167-189, (2002).
「https://ja.wiki.beta.math.wmflabs.org/w/index.php?title=多項式の因数分解&oldid=11721」から取得