多項式の因数分解

数学および計算機代数における多項式の因数分解（いんすうぶんかい、英: 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 \in ℤ [X]$ の内容 " $cont(p)$ " は（符号の違いを除いて） $p$ のすべての係数の最大公約数を言い、 $p$ の原始成分 $prim-part(p) ≔ p /cont(p)$ は整係数の原始多項式である。これらによって $p$ は原始多項式の整数倍という形への分解が定義され、内容の符号の違いを除いて一意に定まる。通常は、内容の符号は原始成分の最高次係数が正となるようにとる。
任意の有理係数多項式 $q$ は $q={\frac {p}{c}}\quad (\exists p\in \mathbb {Z} [X],\exists c\in \mathbb {Z} )$ の形に書き直せる（なんとなれば、 $c$ として $q$ の係数の分母を全てかけ合わせたものをとれば（このとき $p ≔ cq$ は整係数となり）十分である）。このとき $q$ の内容は ${\text{cont}}(q):={\frac {{\text{cont}}(p)}{c}}$ で、また $q$ の原始成分は $p$ のそれで、それぞれ定義する。整係数多項式の場合と同様に、この場合も、有理係数多項式を有理数と整係数原始多項式の積への分解が、符号のとり方を除いて一意に定義される。

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

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

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

無平方分解

→詳細は「無平方多項式（英語版）」を参照

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

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

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

古典的手法

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

一次因子の見つけ方

有理係数の範囲での一次因子は何れも有理根テストによって見つけることができる。すなわち、因数分解したい多項式が ${\textstyle a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}}$ であるとき、取りうる任意の一次因子 ${\textstyle b_{1}x-b_{0}}$ は、 $b 1$ が $a n$ の整数因子かつ $b 0$ は $a 0$ の整数因子でなければならない。そのような整数因子すべての組み合わせについて有効か否か確かめて、有効な因子については筆算（英語版）などして分解を得る。もとの多項式が次数 $2$ 以上の因子を少なくとも二つ含む積であるならば、先に述べた仕方では部分的な分解しか得られないが、そうでなければ完全に一次因子のみの積に分解できることになる。特に、非一次因子がちょうど一つである場合には、それは全ての一次因子を分解し尽くした残りの部分の多項式として取り出せる。三次多項式の場合には、それが完全に因数分解できるならば有理根テストを用いるだけでその分解が決定できる（それは一つの一次因子と二次の既約因子との積であるか、さもなくば三つの一次因子の積である）ことは注目に値する。

クロネッカーの方法

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

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

$f$ を $p$ で割れば、別の因子として ${\textstyle q(x):=x^{3}-x+2}$ を得るから、因数分解 $f = pq$ を得る。さてさらに再帰的に有理根テストを施して $p, q$ をそれぞれ分解しようと試みれば、これらが $ℤ$ 上既約であることがわかるから、これで $f$ の既約因子分解 $f(x)=p(x)q(x)=(x^{2}+x+1)(x^{3}-x+2)$ を得た^[3]。

現代的手法

有限体上の因数分解

→詳細は「有限体上の多項式の因数分解（英語版）」、「バーリカンプのアルゴリズム（英語版）」、および「カントール–ツァッセンハウスのアルゴリズム（英語版）」を参照

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

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

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

まず素数 $p$ を $f (x) mod p$ がやはり無平方かつ次数を落とさないように選んで、 $f (x) mod p$ を因数分解する。これにより、整係数多項式 $f 1, \dots, f r$ でそれらの積が $p$ を法として $f$ に等しいものが得られる。
次に、ヘンゼル持ち上げを適用して、f_i たちがそれらの積がこんどは p^a を法として f と一致するようにできる（ただし、a は p^a が 2B よりも大きくなるように選ぶものとする）。
- この時点で法 $p a$ に関して $f (x)$ は（単数を掛ける違いを除いて） $2 r$ 個の因子を持つ— ${f 1, \dots, f r}$ の任意の部分集合の各々に対して、その元の総積が $f (x) mod p a$ の因子を与える—が、法 $p a$ に関する因子が「真の因子」（すなわち、 $ℤ [x]$ における $f (x)$ の因子）に対応するとは限らないことに注意する。
法 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, α, α 2, \dots

の満たす整係数線型関係式（英語版）（つまり

α

の満たす整係数多項式関係式）を近似的に求めると、それが（近似でない）真の線型関係式の、したがって

f

の多項式因子の候補になる。

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

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

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

体 $K$ が代数体（ $ℚ$ の有限次拡大体）であるときの多項式 $p (x) \in K [x]$ も因数分解することができる。無平方分解して、多項式は無平方であると仮定してよい。 $ℚ$ 上の線型環として $L ≔ K [x]/(p (x))$ と陽に書いて、無作為に $α \in L$ をとれば、原始元定理により、高確率で $α$ は $L$ を $ℚ$ 上生成する。生成することが確認できたならば、 $α$ の $ℚ$ 上の最小多項式 $q (y) \in ℚ [y]$ を計算して、それを $ℚ [y]$ 上で $q(y)=\prod _{i=1}^{n}q_{i}(y)$ と因数分解することで、 $L=\mathbb {Q} [\alpha ]=\mathbb {Q} [y]/(q(y))=\prod _{i=1}^{n}\mathbb {Q} [y]/(q_{i}(y))$ と決定できて（ $p$ は無平方であるから、 $L$ が被約環となることに注意）、 $α$ は右辺の元 $(y, \dots, y)$ （全ての成分が $y$ ）に対応する。これが体の直積としての $L$ の唯一の分解であることに注意する。したがってこの分解は $\prod _{i=1}^{m}K[x]/(p_{i}(x))$ と同じものである（ここに $p = \prod m i =1 p i$ は $p$ の $K [x]$ における既約分解とする）。 $x \in L$ および $K$ の生成元を $α$ の多項式として書けば、 $x$ および $K$ の $ℚ [y]/(q i (y)) = K [x]/(p i (x))$ の直積因子の中への埋め込みが決定できる。この環における $x$ の最小多項式を求めることにより、 $p i$ が計算できて、したがって $p$ が $K$ 上で既約分解される。

注

[脚注の使い方]

注釈

^ おなじことは、 $ℤ$ および $ℚ$ を、(U)FD $R$ およびその商体 $K$ に置き換えてより一般に考察できる

出典

^ FT Schubert: De Inventione Divisorum Nova Acta Academiae Scientiarum Petropolitanae v.11, p. 172-182(1793)
^ 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).
^ van der Waerden 1970, §5.4, 5.6.
^ M. van Hoeij: Factoring polynomials and the knapsack problem. Journal of Number Theory, 95, 167-189, (2002).

参考文献

Fröhlich, A.; Shepherson, J. C. (1955), “On the factorisation of polynomials in a finite number of steps”, Mathematische Zeitschrift 62 (1): 331–334, doi:10.1007/BF01180640, ISSN 0025-5874
Trager, B.M., “Algebraic Factoring and Rational Function Integration”, Proc. SYMSAC 76
Bernard Beauzamy, Per Enflo, Paul Wang (October 1994). “Quantitative Estimates for Polynomials in One or Several Variables: From Analysis and Number Theory to Symbolic and Massively Parallel Computation”. Mathematics Magazine 67 (4): 243–257. doi:10.2307/2690843. JSTOR 2690843. (accessible to readers with undergraduate mathematics)
Cohen, Henri (1993). A course in computational algebraic number theory. Graduate Texts in Mathematics. 138. Berlin, New York: Springer-Verlag. ISBN 978-3-540-55640-4. MR1228206
Kaltofen, Erich (1982), “Factorization of polynomials”, in B. Buchberger; R. Loos; G. Collins, Computer Algebra, Springer Verlag, doi:10.1007/978-3-7091-3406-1_8, MR780381, Zbl 0519.68059
Knuth, Donald E (1997). “4.6.2 Factorization of Polynomials”. Seminumerical Algorithms. The Art of Computer Programming. 2 (Third ed.). Reading, Massachusetts: Addison-Wesley. pp. 439–461, 678–691. ISBN 0-201-89684-2
Lenstra, A. K.; Lenstra, H. W.; Lovász, László (1982). “Factoring polynomials with rational coefficients”. Mathematische Annalen 261 (4): 515–534. doi:10.1007/BF01457454. ISSN 0025-5831. MR682664
van der Waerden, B. L. (1970), Algebra, trans. Blum and Schulenberger, Frederick Ungar