多項式の因数分解

有理係数を持つすべての線形因数は、有理根判定法を用いて求めることができます。因数分解する多項式が${\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}}$整数因数のすべての組み合わせの妥当性をテストでき、有効な組み合わせはそれぞれ多項式の長除法を使用して因数分解できます。元の多項式が、少なくとも 2 つの因数が 2 以上である因数の積である場合、この手法では部分的な因数分解しか得られません。そうでない場合は、因数分解は完全です。特に、非線形因数がちょうど 1 つある場合、それはすべての線形因数を因数分解した後に残る多項式になります。3次多項式の場合、3 次多項式が因数分解可能であれば、有理根テストにより、線形因数と既約 2 次因数、または 3 つの線形因数のいずれかに完全に因数分解されます。

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

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

与えられた次数dのすべての因数を探す場合、${\displaystyle d+1}$価値観、$\displaystyle a_{0},\ldots ,a_{d}}$aに対して、タプルの有限個の可能性を与える${\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})}$は有限個の約数を持つので、そのようなタプルは有限個存在する。したがって、網羅的な探索によって、次数が最大dのすべての約数を見つけることができます。

例えば、

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

この多項式がZ上で因数分解できるならば、その因数の少なくとも 1 つは${\displaystyle p(x)}$次数が２以下でなければならないので、${\displaystyle p(x)}$は3つの値によって一意に決定されます。したがって、3つの値を計算します。${\displaystyle f(0)=2}$、${\displaystyle f(1)=6}$そして${\displaystyle f(-1)=2}$これらの値のいずれかが 0 の場合、線形因子となります。値がゼロでない場合は、それぞれの可能な因数分解を列挙できます。さて、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 )で割ると、もう一方の因数が得られます。${\displaystyle q(x)=x^{3}-x+2}$、 となることによって${\displaystyle f(x)=p(x)q(x)}$。ここで、再帰的にテストして、 p ( x )とq ( x )の因数を求めることができます。この場合は、有理根判定法を使用します。結果として、両方とも既約であることがわかりました。したがって、 f ( x )の既約因数分解は次のようになります。 ^{[ 5 ]}

${\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}$。

ザッセンハウスのアルゴリズムは次のように進められます。まず、素数を選びます。${\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）アルゴリズムの応用である。^{[ 6 ]}

LLL因数分解アルゴリズムの簡略版は次のとおりです。多項式の複素（またはp進）根αを計算します。${\displaystyle f(x)}$高精度で、次にLenstra–Lenstra–Lovász 格子基底縮小アルゴリズムを使用して、 1、α、α ²、α ³ 、... の間の近似線形関係を整数係数で見つけます。これは、正確な線形関係と多項式因子である可能性があります。${\displaystyle f(x)}$この方法では、因数分解または既約性証明のいずれかが得られることを保証する精度の上限を定めることができる。この方法は多項式時間で完了するが、格子が高次元で要素数が非常に大きいため計算が遅くなり、実際には使用されていない。

ザッセンハウスアルゴリズムの指数関数的な複雑さは、組み合わせ問題から生じます。${\displaystyle f_{1}(x),\ldots ,f_{r}(x)}$最先端の因数分解実装は、組み合わせ問題を格子問題に変換し、それを LLL で解く点を除いて、Zassenhaus と同様の方法で動作します。^{[ 7 ]}このアプローチでは、LLL は因数の係数を計算するために使用されるのではなく、ベクトルを計算するために使用されます。${\displaystyle r}${0,1} のエントリは、以下の部分集合をエンコードします。${\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 を明示的に代数として書きます。${\displaystyle \mathbb {Q} }$ランダムな要素を選択します${\displaystyle \alpha \in L}$生成する${\displaystyle L}$以上${\displaystyle \mathbb {Q} }$with high probability by the primitive element theorem. If this is the case, we can compute the minimal polynomial ${\displaystyle q(y)\in \mathbb {Q} [y]}$ of ${\displaystyle \alpha }$ over ${\displaystyle \mathbb {Q} }$, by finding a ${\displaystyle \mathbb {Q} }$-linear relation among 1, α, . . . , αⁿ. Using a factoring algorithm for rational polynomials, we factor into irreducibles in ${\displaystyle \mathbb {Q} [y]}$:

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

Thus we have:

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

where ${\displaystyle \alpha }$ corresponds to ${\displaystyle y\leftrightarrow (y,y,\ldots ,y)}$. This must be isomorphic to the previous decomposition of ${\displaystyle L}$.

The generators of L are x along with the generators of ${\displaystyle K}$ over ${\displaystyle \mathbb {Q} }$; writing these as a polynomials in ${\displaystyle \alpha }$, we can determine the embeddings of ${\displaystyle x}$ and ${\displaystyle K}$ into each component ${\displaystyle \mathbb {Q} [y]/q_{i}(y)=K[x]/p_{i}(x)}$. By finding the minimal polynomial of ${\displaystyle x}$ in ${\displaystyle \mathbb {Q} [y]/q_{i}(y)}$, we compute ${\displaystyle p_{i}(x)}$, and thus factor ${\displaystyle p(x)}$ over ${\displaystyle K.}$

In general, most polynomials do not have square roots. However, some applications, such as the electrical engineers function of obtaining the Y parameters from a driving point impedance of a two port network,^[8] do utilize squared polynomials that must be factored into two identical square root polynomials. The algorithm below will factor a squared polynomial, ${\displaystyle {\sqrt {x^{6}-6x^{5}+17x^{4}-36x^{3}+52x^{2}+48x+36}}}$, into two identical polynomial roots, ${\displaystyle R=X^{3}-3x^{2}+4x-6}$, using an example from Mathematics Stack Exchange.^[9][10]

${\displaystyle {\begin{aligned}&{\begin{array}{|l|l|l|}\hline Q&R&R(2Q+R)\\\hline \\0&x^{3}&x^{6}\\\hline \\x^{3}&-3x^{2}&6x^{5}-9x^{4}\\\hline \\x^{3}-3x^{2}&4x&8x^{4}-24x^{3}+16x^{2}\\\hline \\x^{3}-3x^{2}+4x&-6&-12x^{3}+36x^{2}-48x+36\\\hline \end{array}}&{\begin{array}{|c|c|c|c|c|c|c|c|}\hline R&x^{3}&&-3x^{2}&&4x&&-6\\\hline 1&x^{6}&-6x^{5}&17x^{4}&-36x^{3}&52x^{2}&48x&36\\&x^{6}&&&&&&\\\hline 2&&-6x^{5}&17x^{4}&&&&\\&&-6x^{5}&9x^{4}&&&&\\\hline 3&&&8x^{4}&-36x^{3}&52x^{2}&&\\&&&8x^{4}&-24x^{3}&16x^{2}&&\\\hline 4&&&&-12x^{3}&36x^{2}&-48x&36\\&&&&-12x^{3}&36x^{2}&-48x&36\\\hline \end{array}}\end{aligned}}}$

Steps:

Step1: Compute the square root of the leading term, ${\displaystyle x^{6}}$, and place it, ${\displaystyle x^{3}}$, in the leading term of the solution R polynomial solution row on top, and place the ${\displaystyle x^{6}}$ term in row 1 just below the polynomial to be factored, as shown.

Step2: Subtract the newly placed ${\displaystyle x^{6}}$ from the polynomial to be factored, and bring down the next two terms into row 2.

Step3: Double the current state of the solution R polynomial, then add a new term, Q, such that R(2Q+R) negates the leading term of row 2, and place the negative of R(2Q+R) in the lower space of row 2.

Step4: Subtract the two numbers in row 2, place the results in row 3, and bring down the next two terms of row 1 into row 3..

Step 5: Repeat for all remaining rows and columns until complete.

When complete, the solution R polynomial will show up in the R column in the left side table and the R row of the right side table.