テオドール・フォン・シューベルト 数学 および計算機代数 における多項式の因数分解 （いんすうぶんかい、英 : factorization of polynomial , polynomial factorization 体 あるいは整数 を係数とする多項式 を同じ範囲に係数を持つ既約因子 の積として表すことおよびその過程を言う。多項式の分解は計算機代数システム の基本的なツールの一つである。
多項式の因数分解の歴史は、1793年にテオドール・フォン・シューベルト （ドイツ語版 ） [ 1] レオポルト・クロネッカー が多変数の代数体 係数多項式に対して拡張している。しかし、このトピックにおける知識の大部分は計算機代数システム の登場する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 は
q
=
p
c
(
∃
p
∈
Z
[
X
]
,
∃
c
∈
Z
)
{\displaystyle q={\frac {p}{c}}\quad (\exists p\in \mathbb {Z} [X],\exists c\in \mathbb {Z} )}
c として q の係数の分母を全てかけ合わせたものをとれば（このとき p ≔ cq q の内容 は
cont
(
q
)
:=
cont
(
p
)
c
{\displaystyle {\text{cont}}(q):={\frac {{\text{cont}}(p)}{c}}}
q の原始成分 は p のそれで、それぞれ定義する。整係数多項式の場合と同様に、この場合も、有理係数多項式を有理数と整係数原始多項式の積への分解が、符号のとり方を除いて一意に定義される。 カール・フリードリヒ・ガウス は二つの原始多項式の積がふたたび原始的であること（ガウスの補題 （英語版 ）
言い方を変えれば、整数のGCD計算によって有理係数多項式の因数分解は整係数原始多項式の因数分解に帰着され、また整数環上での因数分解は整数の因数分解と原始多項式の因数分解に帰着することができるようになるということである。
さてここまでに述べたことは、ℤ F 上の多項式環 で、および ℚ F の有理函数 体でそれぞれ置き換えて（ただし置き換え後の両者の不定元は共通とする）、「符号の違いを除いて」という代わりに「F の単元 を掛ける違いを除いて」とすれば、すべてそのまま成り立つ。この場合、F の純超越拡大 体上での因数分解が F 上の多変数多項式 の因数分解に帰着される。
多項式のふたつ以上の因子が互いに一致する場合を考えると、すなわちその多項式はこの因子の平方（平方因子）で割り切れるということになる。一変数多項式の場合だと、そのような因子（多重因子）を与える根は重根 と定義される。またこの場合、その多重因子はもとの多項式の導多項式 （多変数の場合は、どの変数に関する微分でも）の因子になる。有理数体（あるいはより一般に標数 0 の任意の体）上の一変数多項式の場合、David Yun による無平方分解アルゴリズム （英語版 ） 無平方
Yun のアルゴリズムは、多変数多項式を多項式環上の一変数多項式と見ることにより、多変数多項式の場合にも拡張することができる。
有限体上の多項式の場合には、Yun のアルゴリズムは多項式の次数が係数体の標数より小さい場合にのみ適用可能である（これは、そうでない場合には非零多項式の導多項式が零多項式となる場合があることによる。例えば p -元体上で冪函数 xp の導多項式は常に零である）。それでも、多項式とその導多項式の間のGCD計算があれば無平方分解は得られる（有限体上の多項式の因数分解#無平方分解 （英語版 ）
本節では手計算に便利な教科書的方法について述べる。それらは多項式の分解よりも極めて複雑な一面を持つ自然数の因数分解 も利用しているから、計算機に載せるようなものではない。
有理係数の範囲での一次因子は何れも有理根テスト によって見つけることができる。すなわち、因数分解したい多項式が
a
n
x
n
+
a
n
−
1
x
n
−
1
+
⋯
+
a
1
x
+
a
0
{\textstyle a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}}
b
1
x
−
b
0
{\textstyle b_{1}x-b_{0}}
b 1 an の整数因子かつ b 0 a 0 筆算 （英語版 ） 2 以上の因子を少なくとも二つ含む積であるならば、先に述べた仕方では部分的な分解しか得られないが、そうでなければ完全に一次因子のみの積に分解できることになる。特に、非一次因子がちょうど一つである場合には、それは全ての一次因子を分解し尽くした残りの部分の多項式として取り出せる。三次多項式 の場合には、それが完全に因数分解できるならば有理根テストを用いるだけでその分解が決定できる（それは一つの一次因子と二次の既約因子との積であるか、さもなくば三つの一次因子の積である）ことは注目に値する。
整数係数多項式の各整数で評価した値は有限通りの分解しかないので、十分多くの整数での値から因子の候補となる多項式を（補間公式などにより）構成すれば、因子はこれらの有限個の多項式から見つけられる。
例えば
f
(
x
)
:=
x
5
+
x
4
+
x
2
+
x
+
2
{\displaystyle f(x):=x^{5}+x^{4}+x^{2}+x+2}
ℤ f (0) = 2f (1) = 6f (−1) = 20 に等しくなっていたならば、それはすでに根が見つかった（したがって一次因子が得られた）ことになることに注意せよ。0 に等しいものが無いとすれば、それらの因数は有限個である。いまの場合 2 の因数分解は 1×2, 2×1, (−1)×(−2), (−2)×(−1) の四通りだけであるから、もし二次の整係数因子があったならば、その x = 01, 2, −1, −2 の何れかでなければならない。x = −16 の因数分解は 8 通りだから、これらの分解のとり方の組み合わせは 4 × 4 × 8 = 128 通りだが、半分は符号が逆になっただけなので、二次因子となる候補としてチェックすべきものは半分の 64 通りということになる。それ以外のものが f (x )
p
(
x
)
:=
x
2
+
x
+
1
{\displaystyle p(x):=x^{2}+x+1}
p (0) = 1p (1) = 3p (−1) = 1f (x )
f を p で割れば、別の因子として
q
(
x
)
:=
x
3
−
x
+
2
{\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
)
{\displaystyle f(x)=p(x)q(x)=(x^{2}+x+1)(x^{3}-x+2)}
ハンス・ユリウス・ツァッセンハウス
上で見たことを踏まえれば、f (x )一般性を失うことなく それが原始的かつ無平方と仮定してよい。すると初めに考えるべきは f の任意の因子 g のすべての係数の絶対値を抑える上界 B を計算することである。そうして m を 2B より大きな整数として、g (x )m を法として求まったならば、その法 m に関して分かっている g の情報から g が復元できる。
その方法を述べるハンス・ユリウス・ツァッセンハウス （ドイツ語版 ）
まず素数 p を f (x ) mod p f (x ) mod p f 1 , …, fr p を法として f に等しいものが得られる。
次に、ヘンゼル持ち上げ を適用して、fi たちがそれらの積がこんどは pa を法として f と一致するようにできる（ただし、a は pa が 2B よりも大きくなるように選ぶものとする）。
この時点で法 pa に関して f (x )2r 個の因子を持つ— {f 1 , …, fr } の任意の部分集合の各々に対して、その元の総積が f (x ) mod pa pa に関する因子が「真の因子」（すなわち、ℤ [x ]f (x )
法 pa に関する各因子に対してそれが真の因子に対応するものかどうかをテストして、対応するものと分かれば（pa が 2B より大きいという仮定のもと）真の因子を計算することになる。
この方法では、高々 2r 通りをチェックすれば真の既約因子をすべて見つけることができる（各因子の補因子—掛けて f (x ) になるもう一方の因子—についてのチェックは飛ばせるから、実際には 2r −1 通りでよい）。f (x )fi についてはチェックを飛ばせるので、調べるべき場合の数はさらに減らすことができる。 ツァッセンハウスのアルゴリズムは各場合のチェックについては手早くできるが、その場合の数が最悪の場合では指数函数的に大きくなってしまう。
有理係数多項式の因数分解を多項式時間 で計算できる最初のアルゴリズムは Lenstra, Lenstra & Lovász (1982) が格子基底縮小アルゴリズム （英語版 ）
多項式 f の複素（あるいは p -進）根 α を高精度で計算し、LLL格子基底縮小アルゴリズムを用いて 1, α , α 2 , … 整係数線型関係式 （英語版 ） α の満たす整係数多項式関係式）を近似的に求めると、それが（近似でない）真の線型関係式の、したがって f の多項式因子の候補になる。 適切に近似の精度の限界を決めることで、このアルゴリズムが多項式因子か既約性証明の何れかを与えるものであることを保証することができる。この方法は多項式時間であるけれども、格子は高次元のもので、成分数は膨大になり、計算に時間がとられることを考えれば、実用に供されるものではない。
さて、ツァッセンハウスのアルゴリズムの計算量が指数時間となるのは、（f 1 , …, fr [ 4] {0, 1} に r 個の成分をとるベクトル（真の既約因子を与える f 1 , …, fr
体 K が代数体 （ℚ p (x ) ∈ K [x ]無平方分解 して、多項式は無平方であると仮定してよい。ℚ L ≔ K [x ]/(p (x ))α ∈ L 原始元定理 により、高確率で α は L を ℚ α の ℚ 最小多項式 q (y ) ∈ ℚ [y ]ℚ [y ]
q
(
y
)
=
∏
i
=
1
n
q
i
(
y
)
{\displaystyle q(y)=\prod _{i=1}^{n}q_{i}(y)}
L
=
Q
[
α
]
=
Q
[
y
]
/
(
q
(
y
)
)
=
∏
i
=
1
n
Q
[
y
]
/
(
q
i
(
y
)
)
{\displaystyle L=\mathbb {Q} [\alpha ]=\mathbb {Q} [y]/(q(y))=\prod _{i=1}^{n}\mathbb {Q} [y]/(q_{i}(y))}
p は無平方であるから、L が被約環 となることに注意）、α は右辺の元 (y , …, y ) （全ての成分が y ）に対応する。これが体の直積としての L の唯一の分解であることに注意する。したがってこの分解は
∏
i
=
1
m
K
[
x
]
/
(
p
i
(
x
)
)
{\displaystyle \prod _{i=1}^{m}K[x]/(p_{i}(x))}
p = ∏m i =1pi p の K [x ]x ∈ L K の生成元を α の多項式として書けば、x および K の ℚ [y ]/(qi (y )) = K [x ]/(pi (x ))x の最小多項式を求めることにより、pi が計算できて、したがって 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).
^ 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 , http://dl.acm.org/citation.cfm?id=806338 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 . 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 . MR 1228206 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 , MR 780381 , 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 . MR 682664 van der Waerden, B. L. (1970), Algebra , trans. Blum and Schulenberger, Frederick Ungar
Kaltofen, Erich (1990), “Polynomial Factorization 1982-1986”, in D. V. Chudnovsky; R. D. Jenks, Computers in Mathematics , Lecture Notes in Pure and Applied Mathematics, 125 , Marcel Dekker, Inc. Kaltofen, Erich (1992), “Polynomial Factorization 1987–1991” , Proceedings of Latin ’92 , Springer Lect. Notes Comput. Sci., 583 , Springer, http://www4.ncsu.edu/~kaltofen/bibliography/92/Ka92_latin.pdf October 14, 2012 閲覧。 Ivanyos, Gabor; Marek, Karpinski; Saxena, Nitin (2009), “Schemes for Deterministic Polynomial Factoring”, Proc. ISSAC 2009 : 191–198, arXiv :0804.1974 , doi :10.1145/1576702.1576730
Weisstein, Eric W. "Polynomial Factorization" . mathworld.wolfram.com (英語). factorization of primitive polynomial PlanetMath .（英語） Hazewinkel, Michiel, ed. (2001), “Factorization of polynomials” , Encyclopedia of Mathematics ISBN 978-1-55608-010-4 , https://www.encyclopediaofmath.org/index.php?title=Factorization_of_polynomials Hazewinkel, Michiel, ed. (2001), “Kronecker method” , Encyclopedia of Mathematics ISBN 978-1-55608-010-4 , https://www.encyclopediaofmath.org/index.php?title=Kronecker_method
.jpg)
![{\displaystyle q={\frac {p}{c}}\quad (\exists p\in \mathbb {Z} [X],\exists c\in \mathbb {Z} )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dec016913ae637ec1747e77886bd5a22f0fc1693)
![{\displaystyle L=\mathbb {Q} [\alpha ]=\mathbb {Q} [y]/(q(y))=\prod _{i=1}^{n}\mathbb {Q} [y]/(q_{i}(y))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/996f1b83cbe4eaa28d537eb7873dc0fbc400a2aa)
![{\displaystyle \prod _{i=1}^{m}K[x]/(p_{i}(x))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5b0737de927bb96b7c57e53b7803cf5d491d2810)
