多項式の因数分解

ウィキペディア

多項式の因数分解

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/06/30 01:44 UTC 版)

テオドール・フォン・シューベルト

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

多項式の因数分解の歴史は、1793年にテオドール・フォン・シューベルト（ドイツ語版）が多項式の分解アルゴリズムを記述したこと^[1]に始まり、それを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次より上で数千ディジットの係数を持つ場合でも整係数一変数多項式を素早く因数分解することができる^[2]。

問題の定式化について

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

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

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

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

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

および

• 多変数多項式から一変数の場合への還元
• 純超越拡大体（英語版）係数から基礎体上多変数の場合への還元（後述）
• 代数拡大体係数から基礎体係数への還元（後述）
• 有理係数から整係数への還元（後述）
• 整係数から（うまく選んだ素数 p に対する）p-元体係数への還元（後述）

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

内容–原始成分分解

「内容 (多項式)」および「ガウスの補題 (多項式)（英語版）」も参照

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

• 整係数多項式 p ∈ ℤ[X] の内容 "cont(p)" は（符号の違いを除いて）p のすべての係数の最大公約数を言い、p の原始成分 prim-part(p) ≔ p/cont(p) は整係数の原始多項式である。これらによって p は原始多項式の整数倍という形への分解が定義され、内容の符号の違いを除いて一意に定まる。通常は、内容の符号は原始成分の最高次係数が正となるようにとる。
• 任意の有理係数多項式 q は $${\displaystyle q={\frac {p}{c}}\quad (\exists p\in \mathbb {Z} [X],\exists c\in \mathbb {Z} )}$$
  ハンス・ユリウス・ツァッセンハウス

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

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

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

  1. まず素数 p を f(x) mod p がやはり無平方かつ次数を落とさないように選んで、f(x) mod p を因数分解する。これにより、整係数多項式 f₁, …, f_r でそれらの積が p を法として f に等しいものが得られる。
  2. 次に、ヘンゼル持ち上げを適用して、f_i たちがそれらの積がこんどは p^a を法として f と一致するようにできる（ただし、a は p^a が 2B よりも大きくなるように選ぶものとする）。
     • この時点で法 p^a に関して f(x) は（単数を掛ける違いを除いて）2^r 個の因子を持つ— {f₁, …, f_r} の任意の部分集合の各々に対して、その元の総積が f(x) mod p^a の因子を与える—が、法 p^a に関する因子が「真の因子」（すなわち、ℤ[x] における f(x) の因子）に対応するとは限らないことに注意する。
  3. 法 p^a に関する各因子に対してそれが真の因子に対応するものかどうかをテストして、対応するものと分かれば（p^a が 2B より大きいという仮定のもと）真の因子を計算することになる。
     • この方法では、高々 2^r 通りをチェックすれば真の既約因子をすべて見つけることができる（各因子の補因子—掛けて f(x) になるもう一方の因子—についてのチェックは飛ばせるから、実際には 2^r−1 通りでよい）。f(x) が可約のときは、既に真の因子であるとわかっている f_i についてはチェックを飛ばせるので、調べるべき場合の数はさらに減らすことができる。

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

  有理係数多項式の因数分解を多項式時間で計算できる最初のアルゴリズムは Lenstra, Lenstra & Lovász (1982) が格子基底縮小アルゴリズム（英語版）（"LLLアルゴリズム"）の応用として与えた。簡易版のLLL因数分解アルゴリズムは以下のようなものである:

  多項式 f の複素（あるいは p-進）根 α を高精度で計算し、LLL格子基底縮小アルゴリズムを用いて 1, α, α², … の満たす整係数線型関係式（英語版）（つまり α の満たす整係数多項式関係式）を近似的に求めると、それが（近似でない）真の線型関係式の、したがって f の多項式因子の候補になる。

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

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

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

  体 K が代数体（ℚ の有限次拡大体）であるときの多項式 p(x) ∈ K[x] も因数分解することができる。無平方分解して、多項式は無平方であると仮定してよい。ℚ 上の線型環として L ≔ K[x]/(p(x)) と陽に書いて、無作為に α ∈ L をとれば、原始元定理により、高確率で α は L を ℚ 上生成する。生成することが確認できたならば、α の ℚ 上の最小多項式 q(y) ∈ ℚ[y] を計算して、それを ℚ[y] 上で$${\displaystyle q(y)=\prod _{i=1}^{n}q_{i}(y)}$$ カテゴリ