数学および計算機代数における多項式の因数分解（いんすうぶんかい、英: 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) を係数とし、算術的演算を用いたアルゴリズムが存在する場合にのみ意味をなす。(Frohlich & 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}} は、b1 が an の整数因子かつ b0 は a0 の整数因子でなければならない。そのような整数因子すべての組み合わせについて有効か否か確かめて、有効な因子については筆算（英語版）などして分解を得る。もとの多項式が次数 2 以上の因子を少なくとも二つ含む積であるならば、先に述べた仕方では部分的な分解しか得られないが、そうでなければ完全に一次因子のみの積に分解できることになる。特に、非一次因子がちょうど一つである場合には、それは全ての一次因子を分解し尽くした残りの部分の多項式として取り出せる。三次多項式の場合には、それが完全に因数分解できるならば有理根テストを用いるだけでその分解が決定できる（それは一つの一次因子と二次の既約因子との積であるか、さもなくば三つの一次因子の積である）ことは注目に値する。
クロネッカーの方法

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

例えば f ( x ) := x 5 + x 4 + x 2 + x + 2 {\displaystyle f(x):=x^{5}+x^{4}+x^{2}+x+2} を考えるとき、これが ? 上で分解するならば、その因子の少なくとも一つは二次以下である。