多項式の因数分解

数学とコンピュータ代数において、多項式の因数分解または多項式因数分解は、与えられた体または整数内の係数を持つ多項式を、同じ領域内の係数を持つ既約因数の積として 表現します。多項式因数分解は、コンピュータ代数システムの基本コンポーネントの 1 つです。

最初の多項式因数分解アルゴリズムは、1793年にテオドール・フォン・シューベルトによって発表されました。 ^[1] レオポルド・クロネッカーは1882年にシューベルトのアルゴリズムを再発見し、代数拡張で多変数多項式と係数に拡張しました。しかし、このトピックに関する知識のほとんどは、1965年頃と最初のコンピュータ代数システムより古くはありません。^[2]

以前から知られていた有限ステップ アルゴリズムが初めてコンピュータに導入されたとき、その効率が非常に悪いことが判明しました。100 次までの単変数または多変数多項式で、係数が中程度 (100 ビットまで) のものは、最新のアルゴリズムで数分のコンピュータ時間で因数分解できるという事実は、この問題が過去 15 年間でいかにうまく解決されてきたかを示しています。(Erich Kaltofen、1982 年)

現代のアルゴリズムとコンピュータは、数千桁の係数を持つ1000次以上の一変数多項式を素早く因数分解することができます。^{[3]この目的のために、}有理数と数体 上の因数分解の場合でも、有限体上の多項式の因数分解が基本的なステップとなります。

整数または体上の多項式環は、一意の因数分解領域です。つまり、これらの環のすべての要素は、定数の積と既約多項式（2 つの非定数多項式の積ではないもの）の積です。さらに、この分解は、因数を可逆定数で乗算するまで一意です。

因数分解は基底体に依存します。たとえば、複素係数を持つすべての多項式は複素根を持つという代数の基本定理は、整数係数を持つ多項式が（根を求めるアルゴリズムを使用して）複素体C上の線型因数に因数分解できることを意味します。同様に、実数体上では、既約因数の次数は最大で 2 ですが、有理数体Q上では、任意の次数の多項式が既約になります。

多項式因数分解の問題は、すべての要素がコンピュータで表現でき、算術演算のアルゴリズムが存在する計算可能体の係数に対してのみ意味を持ちます。しかし、これは十分な条件ではありません。FröhlichとShepherdsonは、因数分解アルゴリズムが存在しないような体の例を示しています。^[4]

因数分解アルゴリズムが知られている係数体には、素体（つまり、有理数の体と素数を法とする整数の体）とその有限生成体の拡大が含まれます。整数係数も扱いやすいです。クロネッカーの古典的な方法は歴史的な観点からのみ興味深いものですが、現代のアルゴリズムは次のような一連の手順で進められます。

• 平方根のない因数分解
• 有限体上の因数分解

および削減:

• 多変量の場合から単変量の場合へ。
• 純粋に超越的な拡張における係数から基底体上の多変量ケースへ (下記参照)。
• 代数拡張の係数から基底体の係数へ (下記参照)。
• 有理係数から整数係数へ（下記参照）。
• 整数係数から、適切に選択されたpに対するp元を持つ素数体の係数へ(以下を参照)。

このセクションでは、 Q (有理数) とZ (整数) の因数分解が本質的に同じ問題であることを示します。

多項式p ∈ Z [ X ] の内容は「cont( p )」と表記され、その符号を除けば、その係数の最大公約数です。pの原始部分はprimpart( p ) =  p /cont( p ) であり、これは整数係数を持つ原始多項式です。これは、 pを整数と原始多項式の積に因数分解することを定義します。この因数分解は、内容の符号を除けば一意です。内容の符号は、原始部分の先頭の係数が正になるように選択するのが通常の慣例です。

例えば、

${\displaystyle -10x^{2}+5x+5=(-5)(2x^{2}-x-1)\,}$

コンテンツとプリミティブ部分に因数分解されます。

有理係数を持つすべての多項式qは次のように書ける。

${\displaystyle q={\frac {p}{c}},}$

ここでp ∈ Z [ X ] かつc ∈ Z : c はqの係数のすべての分母の倍数（たとえばそれらの積）をとり、 p = cqとすれば十分である。qの内容は次のように定義される。

${\displaystyle {\text{cont}}(q)={\frac {{\text{cont}}(p)}{c}},}$

qの原始部分はpの原始部分です。整数係数の多項式に関しては、これは有理数と整数係数の原始多項式への因数分解を定義します。この因数分解も、符号の選択まで一意です。

例えば、

${\displaystyle {\frac {x^{5}}{3}}+{\frac {7x^{2}}{2}}+2x+1={\frac {2x^{5}+21x^{2}+12x+6}{6}}}$

コンテンツとプリミティブ部分に因数分解されます。

ガウスは、2 つの原始多項式の積も原始的であることを証明しました (ガウスの補題)。これは、原始多項式が有理数上で既約である場合、かつそれが整数上で既約である場合に限り、原始多項式が有理数上で既約であることを意味します。これはまた、有理数係数を持つ多項式の有理数上での因数分解が、その原始部分の整数上での因数分解と同じであることを意味します。同様に、整数係数を持つ多項式の整数上での因数分解は、その原始部分の因数分解とその内容の因数分解の積です。

言い換えると、整数 GCD 計算は、有理数上の多項式の因数分解を整数係数を持つ原始多項式の因数分解に縮小し、整数上の因数分解を整数と原始多項式の因数分解に縮小します。

Z を体F上の多項式環に置き換え、Q を同じ変数のF上の有理関数体に置き換えても、前述のすべては真のままです。ただし、「符号まで」を「 F内の可逆定数による乗算まで」に置き換える必要があるという違いがあります。これにより、 Fの純粋に超越的な体拡張上の因数分解が、 F上の多変数多項式の因数分解に簡略化されます。

多項式の 2 つ以上の因数が同一である場合、多項式はこの因数の平方の倍数になります。倍数因数は、多項式の導関数の因数でもあります(変数が複数ある場合は、その変数のいずれかに関して)。

一変数多項式の場合、多重因数は多重根に相当します(適切な拡大体上)。有理数上の (またはより一般的には特性0 の体上の) 一変数多項式の場合、Yun のアルゴリズムはこれを利用して、 gcd( f ( x ), f '( x )) から始まる一連のGCD計算を実行し、多項式を平方のない因数、つまり平方の倍数ではない因数に効率的に因数分解します。最初の多項式を因数分解するには、平方のない因数をそれぞれ因数分解するだけで十分です。したがって、平方のない因数分解は、ほとんどの多項式因数分解アルゴリズムの最初のステップです。

Yun のアルゴリズムは、多変数多項式を多項式環上の単変数多項式として考えることにより、これを多変数の場合に拡張します。

有限体上の多項式の場合、Yun のアルゴリズムは次数が特性より小さい場合にのみ適用されます。そうでない場合、非ゼロ多項式の導関数はゼロになる可能性があるからです ( p個の元を持つ体上では、 x ^pの多項式の導関数は常にゼロです)。それでも、多項式とその導関数から始まる一連の GCD 計算により、平方自由分解を計算できます。有限体上の多項式因数分解#平方自由分解を参照してください。

このセクションでは、手作業で計算するときに便利な教科書的な方法について説明します。これらの方法は、現時点では多項式因数分解よりも遅い整数因数分解を使用するため、コンピューター計算には使用されません。

次の 2 つの方法は、整数係数を持つ一変量多項式から始めて、同じく整数係数を持つ多項式である因子を見つけます。

有理係数を持つすべての線形因数は、有理根テストを使って見つけることができます。因数分解する多項式が の場合、すべての可能な線形因数は の形式になります。ここで、は の整数因数で、 はの整数因数です。整数因数のすべての可能な組み合わせの有効性をテストし、有効な各因数を多項式の長除法を使用して因数分解することができます。元の多項式が、少なくとも 2 つの次数が 2 以上の因数の積である場合、この手法では部分的な因数分解しか提供されませんが、それ以外の場合は因数分解は完全です。特に、非線形因数が 1 つだけである場合、それはすべての線形因数が因数分解された後に残った多項式になります。3 次多項式 の場合、 3 次が因数分解可能であれば、有理根テストによって、1 つの線形因数と既約な 2 次因数、または 3 つの線形因数への完全な因数分解が提供されます。 ${\displaystyle a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}}$${\displaystyle b_{1}x-b_{0}}$${\displaystyle b_{1}}$${\displaystyle a_{n}}$${\displaystyle b_{0}}$${\displaystyle a_{0}}$

クロネッカー法は、整数係数を持つ一変数多項式を整数係数を持つ多項式に因数分解することを目的としています。

この方法は、整数値で整数多項式を評価すると必ず整数が生成されるという事実を利用しています。つまり、 が整数係数の多項式である場合、aが整数であれば は整数になります。 aの因数として取り得る整数値は有限個しかありません。したがって、が の因数である場合、 の値はの因数の 1 つでなければなりません。${\displaystyle f(x)}$${\displaystyle f(a)}$${\displaystyle g(x)}$${\displaystyle f(x),}$${\displaystyle g(a)}$${\displaystyle f(a).}$

与えられた次数dのすべての因数を検索する場合、aについて、組の有限個の可能性を与える値 を検討することができます。各 には有限個の約数 があり、エントリが の約数である各 -組、つまり形式 の組は、最大 次数の一意の多項式を生成します。これは、多項式補間によって計算できます。これらの各多項式は、多項式除算によって因数であるかどうかをテストできます。 は有限個あり、それぞれ には有限個の約数があるため、そのような組は有限個存在します。したがって、網羅的な検索により、最大 次数dのすべての因数を見つけることができます。 ${\displaystyle d+1}$${\displaystyle a_{0},\ldots ,a_{d}}$ ${\displaystyle (f(a_{0}),\ldots ,f(a_{d})).}$${\displaystyle f(a_{i})}$${\displaystyle b_{i,0},\ldots ,b_{i,k_{i}}}$${\displaystyle (d+1)}$${\displaystyle i^{\text{th}}}$${\displaystyle f(a_{i})}$${\displaystyle (b_{0,j_{1}},\ldots ,b_{d,j_{d}})}$${\displaystyle d}$${\displaystyle a_{i}}$${\displaystyle f(a_{i})}$

例えば、

${\displaystyle f(x)=x^{5}+x^{4}+x^{2}+x+2}$。

この多項式がZについて因数分解される場合、少なくともその因数の 1 つは次数 2 以下でなければならないため、 は3 つの値 によって一意に決定されます。したがって、 、の3 つの値を計算し、これらの値の 1 つが 0 の場合、線形因数になります。値が 0 でない場合、それぞれについて可能な因数分解をリストできます。ここで、 2 は次のように因数分解できます。 ${\displaystyle p(x)}$${\displaystyle p(x)}$${\displaystyle f(0)=2}$${\displaystyle f(1)=6}$${\displaystyle f(-1)=2}$

1×2、2×1、(−1)×(−2)、または(−2)×(−1)。

したがって、2次の整数多項式因子が存在する場合、それは次のいずれかの値を取る必要があります。

p (0) = 1、2、−1、または−2

p (1)についても同様です。6 の因数分解は 8 通りあり (1×6 と 2×3 にそれぞれ 4 通り)、合計 4×4×8 = 128 通りの可能な 3 組 ( p (0), p (1), p (-1)) があり、そのうち半分は残りの半分の負数として捨てることができます。したがって、64 通りの明示的な整数多項式を の可能な因数として調べる必要があります。それらを徹底的にテストすると、 次のことがわかります。${\displaystyle p(x)=ax^{2}+bx+c}$${\displaystyle f(x)}$

${\displaystyle p(x)=x^{2}+x+1}$

( g (0), g (1), g (−1)) = (1,3,1)個の因子から構成される。 ${\displaystyle f(x)}$

f ( x ) をp ( x ) で割るともう 1 つの因数 が得られるので、 となる。ここで、 p ( x ) とq ( x )の因数を見つけるために、この場合は有理根テストを使用して再帰的にテストすることができる。 どちらも既約であることが判明したので、 f ( x )の既約因数分解は次のようになる: ^[5]${\displaystyle q(x)=x^{3}-x+2}$${\displaystyle f(x)=p(x)q(x)}$

${\displaystyle f(x)=p(x)q(x)=(x^{2}+x+1)(x^{3}-x+2).}$

が整数上の一変数多項式であり、内容がなく平方がないと仮定すると、任意の因子の絶対値の係数が で制限されるような境界を計算することから始めます。このように、 がより大きい整数であり、 がを法として知られている場合、 を法とするその像から を再構築できます。 ${\displaystyle f(x)}$${\displaystyle B}$${\displaystyle g(x)}$${\displaystyle B}$${\displaystyle m}$${\displaystyle 2B}$${\displaystyle g(x)}$${\displaystyle m}$${\displaystyle g(x)}$${\displaystyle m}$

Zassenhausアルゴリズムは次のように進行します。まず、の像が平方でないままで、 と同じ次数であるような素数を選択します。次に を因数分解します。これにより、積が に一致する整数多項式が生成されます。次に、ヘンゼル リフティングを適用します。これにより が更新され、積が に一致します。ここで はを超えるほど大きいため、それぞれは明確に定義された整数多項式に対応します。 を法として、多項式には因数 (単位まで)が含まれます。これは、 のすべてのサブセットの積です。 を法とするこれらの因数はの「真の」因数に対応する必要はありませんが、 での除算によって簡単にテストできます。このようにして、ほとんどの場合 をチェックすることで、すべての既約な真の因数を見つけることができ、補数をスキップすることで に減らすことができます。 が既約である場合、すでに見つかった真の因数に現れるものを削除することで、ケース数がさらに削減されます。Zassenhaus アルゴリズムは各ケース (各サブセット) を迅速に処理しますが、最悪の場合、指数関数的な数のケースを考慮します。 ${\displaystyle p}$${\displaystyle f(x){\bmod {p}}}$${\displaystyle f(x)}$${\displaystyle f(x){\bmod {p}}}$${\displaystyle f_{1}(x),\ldots ,f_{r}(x)}$${\displaystyle f(x){\bmod {p}}}$${\displaystyle f_{i}(x)}$${\displaystyle f(x){\bmod {p}}^{a}}$${\displaystyle a}$${\displaystyle p^{a}}$${\displaystyle 2B}$${\displaystyle f_{i}(x)}$${\displaystyle p^{a}}$${\displaystyle f(x)}$${\displaystyle 2^{r}}$${\displaystyle \{f_{1}(x),\ldots ,f_{r}(x)\}{\bmod {p}}^{a}}$${\displaystyle p^{a}}$${\displaystyle f(x)}$${\displaystyle \mathbb {Z} [x]}$${\displaystyle \mathbb {Z} [x]}$${\displaystyle 2^{r}}$${\displaystyle 2^{r-1}}$${\displaystyle f(x)}$${\displaystyle f_{i}(x)}$

有理多項式を因数分解する最初の多項式時間アルゴリズムは、Lenstra、Lenstra、および Lovász によって発見され、 Lenstra–Lenstra–Lovász 格子基底簡約(LLL) アルゴリズム (Lenstra、Lenstra、Lovász 1982) の応用です。LLL 因数分解アルゴリズムの簡略版は次のとおりです。多項式の複素数 (またはp進) 根 α を高精度で計算し、次にLenstra–Lenstra–Lovász 格子基底簡約アルゴリズムを使用して、整数係数を持つ1、α、α ²、α ³ 、... の間の近似線形関係を見つけます。これは、正確な線形関係と の多項式因数である可能性があります。この方法が因数または既約性の証明のいずれかを生成することを保証する精度の境界を決定できます。この方法は多項式時間で終了しますが、格子の次元が高く、エントリが巨大であるため計算が遅くなるため、実際には使用されません。 ${\displaystyle f(x)}$${\displaystyle f(x)}$

Zassenhaus アルゴリズムの指数関数的な複雑さは、 の正しいサブセットをどのように選択するかという組み合わせ問題に起因します。最先端の因数分解の実装は Zassenhaus と同様の方法で動作しますが、組み合わせ問題が格子問題に変換され、それが LLL によって解決される点が異なります。^[6]このアプローチでは、LLL は因数の係数を計算するために使用されるのではなく、既約な真の因数に対応する のサブセットをエンコードする {0,1} のエントリを持つベクトルを計算するために使用されます。${\displaystyle f_{1}(x),\ldots ,f_{r}(x)}$${\displaystyle r}$${\displaystyle f_{1}(x),\ldots ,f_{r}(x)}$

多項式 を因数分解することができます。ここで、体はの有限拡大です。まず、平方なし因数分解を使用して、多項式が平方なしであると仮定します。次に、次数 の商環を定義します。これは、が既約でない限り体ではありませんが、が平方なしであるため、被約環です。実際、${\displaystyle p(x)\in K[x]}$${\displaystyle K}$${\displaystyle \mathbb {Q} }$ ${\displaystyle L=K[x]/p(x)}$${\displaystyle n=[L:\mathbb {Q} ]=\deg p(x)\,[K:\mathbb {Q} ]}$${\displaystyle p(x)}$${\displaystyle p(x)}$

${\displaystyle p(x)=\prod _{i=1}^{m}p_{i}(x)}$

がp ( x )の望ましい因数分解である場合、環は次のように一意に体に分解されます。

${\displaystyle L=K[x]/p(x)\cong \prod _{i=1}^{m}K[x]/p_{i}(x).}$

この分解は因数分解を知らなくても求められます。まず、L を上の代数として明示的に記述します。つまり、原始元定理により を高い確率で生成するランダムな元 を選びます。この場合、1、α、...、α ⁿの間の -線形関係を見つけることで、上のの最小多項式を計算できます。有理多項式の因数分解アルゴリズムを使用して、 の既約数を因数分解します。 ${\displaystyle \mathbb {Q} }$${\displaystyle \alpha \in L}$${\displaystyle L}$${\displaystyle \mathbb {Q} }$${\displaystyle q(y)\in \mathbb {Q} [y]}$${\displaystyle \alpha }$${\displaystyle \mathbb {Q} }$${\displaystyle \mathbb {Q} }$${\displaystyle \mathbb {Q} [y]}$

${\displaystyle q(y)=\prod _{i=1}^{n}q_{i}(y).}$

したがって次のようになります:

${\displaystyle L\cong \mathbb {Q} [y]/q(y)\cong \prod _{i=1}^{n}\mathbb {Q} [y]/q_{i}(y),}$

ここで はに対応します。これは の前の分解と同型でなければなりません。 ${\displaystyle \alpha }$${\displaystyle y\leftrightarrow (y,y,\ldots ,y)}$${\displaystyle L}$

Lの生成元はxと上のの生成元です。これらを の多項式として書き表すと、と の各要素への埋め込みを決定できます。のの最小多項式を見つけることでを計算し、 を因数分解します。${\displaystyle K}$${\displaystyle \mathbb {Q} }$${\displaystyle \alpha }$${\displaystyle x}$${\displaystyle K}$${\displaystyle \mathbb {Q} [y]/q_{i}(y)=K[x]/p_{i}(x)}$${\displaystyle x}$${\displaystyle \mathbb {Q} [y]/q_{i}(y)}$${\displaystyle p_{i}(x)}$${\displaystyle p(x)}$${\displaystyle K.}$

「数値因数分解」とは、一般的には実数または複素数の係数を持つ多項式の因数分解を指します。これらの係数は、通常、浮動小数点数として表されるため、近似値しかわかりません。

複素係数を持つ一変数多項式の場合、因数分解は多項式の根と重複度の数値計算に簡単に還元できます。

多変量の場合、係数のランダムな微小摂動により、多くの因数を持つ多項式から始めても、確率 1 で既約多項式が生成されます。したがって、数値因数分解の意味を正確に明確にする必要があります。

を複素係数を持つ既約因数分解多項式とする 。${\displaystyle p}$

${\displaystyle p=\alpha p_{1}^{m_{1}}\cdots p_{k}^{m_{k}}}$

ここで、および因子は複素係数を持つ既約多項式です。 は、係数が の係数に近い多項式で近似されていると仮定します。 の正確な因数分解は、一般に既約ではないため無意味です。の数値因数分解と呼ばれるものには、いくつかの定義があります。${\displaystyle \alpha \in C}$${\displaystyle p_{1},\ldots ,p_{k}}$${\displaystyle p}$${\displaystyle {\tilde {p}}}$${\displaystyle p}$${\displaystyle {\tilde {p}}}$${\displaystyle {\tilde {p}}.}$

とがわかっている場合、近似因数分解は、上記のように因数分解される多項式に近いものを見つけることです。因数分解スキームがわからない場合は、識別が必要になります。たとえば、多項式の既約因数の数は、その Ruppert 行列のゼロです。^[7]したがって、数値 GCD 計算と Ruppert 行列のランク表示による平方フリー因数分解によって、 重複度を識別できます。${\displaystyle k}$${\displaystyle m_{i}}$${\displaystyle {\tilde {p}}}$${\displaystyle m_{1},\ldots ,m_{k}}$${\displaystyle m_{1},\ldots ,m_{k}}$

数値因数分解は現在も研究が進められており、いくつかのアルゴリズムが開発され実装されている。^{[8] [9]}

• 因数分解 § 多項式、基本的なヒューリスティック手法と明示的な公式
• スウィナートン・ダイアー多項式、ザッセンハウス法で最悪の実行時間を持つ多項式の族

• フレーリッヒ、A. Shepherson, JC (1955)、「有限数ステップにおける多項式の因数分解について」、Mathematische Zeitschrift、62 (1): 331–334、doi :10.1007/BF01180640、ISSN  0025-5874、S2CID  119955899
• Trager, BM (1976)。「代数的因数分解と有理関数積分」。記号および代数計算に関する第 3 回 ACM シンポジウム議事録- SYMSAC '76。pp. 219–226。doi : 10.1145 /800205.806338。ISBN 9781450377904. S2CID  16567619。
• Bernard Beauzamy、Per Enflo 、 Paul Wang (1994 年 10 月)。「1 つまたは複数の変数の多項式の定量的推定: 解析と数論から記号および超並列計算まで」。Mathematics Magazine。67 ( 4) : 243–257。doi :10.2307 / 2690843。JSTOR  2690843。{{cite journal}}: CS1 maint: multiple names: authors list (link)（学部レベルの数学を学んだ読者が閲覧可能）
• コーエン、アンリ（1993）。計算代数的数論のコース。数学の大学院テキスト。第138巻。ベルリン、ニューヨーク：シュプリンガー・フェアラーク。ISBN 978-3-540-55640-4. MR  1228206。
• Kaltofen、Erich (1982)、「多項式の因数分解」、B. Buchberger; R. ルース; G. Collins (編)、Computer Algebra、Springer Verlag、95–113 ページ、CiteSeerX  10.1.1.39.7916
• Knuth, Donald E (1997)。「4.6.2 多項式の因数分解」。半数値アルゴリズム。コンピュータプログラミングの技法。第 2 巻 (第 3 版)。マサチューセッツ州レディング: Addison-Wesley。pp. 439–461, 678–691。ISBN 978-0-201-89684-8。
• レンストラ, アラスカ州;レンストラ、ハイウェイ州。ロヴァーシュ、ラースロー(1982)。 「有理係数による多項式の因数分解」。数学アンナレン。261 (4): 515–534。CiteSeerX  10.1.1.310.318。土井：10.1007/BF01457454。ISSN  0025-5831。MR  0682664。S2CID  5701340 。
• Van der Waerden、代数(1970)、トランス。ブルームとシューレンベルガー、フレデリック・アンガー。

• カルトフェン、エリック (1990)、「多項式因数分解 1982-1986」、DV チュドノフスキー、RD ジェンクス (編)、『数学におけるコンピューター』、『純粋および応用数学の講義ノート』、第 125 巻、Marcel Dekker, Inc.、CiteSeerX  10.1.1.68.7461
• カルトフェン、エリック (1992)、「Polynomial Factorization 1987–1991」(PDF)、Proceedings of Latin '92、Springer Lect. Notes Comput. Sci.、vol. 583、Springer 、 2012 年10 月 14 日取得
• Ivanyos, Gabor; Marek, Karpinski; Saxena, Nitin (2009)。「決定論的多項式因数分解のスキーム」。2009国際シンポジウム「記号および代数計算」の議事録。pp . 191–198。arXiv : 0804.1974。doi : 10.1145 / 1576702.1576730。ISBN 9781605586090.S2CID 15895636  。