因数分解

数学における因数分解（いんすうぶんかい、英: factorization, factoring, decomposition; 分解、因子分解）は、与えられた数学的対象を同種の（しかし普通はより小さいあるいはより平易な）別の対象—それは因数（factor; 因子、乗法因子、乗因子）と呼ばれる—の積として書き表すことを言う。たとえば、15 という数は 3 × 5 という因数の積に分解され、多項式 x2 − 4 は (x − 2)(x + 2) という因数の積に分解される。 因子への分解は、除法が自由にできる体系（可除環など）ではほとんどの場合に意味を為さない。例えば実数や複素数の体系において任意の x は y が零でない限り何であっても xy × (1/y) のように分解できることは明らかである（つまり、どの元もいくらでも分解できて、積としての表示を無数に持つ）。しかし例えば、有理数や有理関数の成す体系ならば、分子と分母を別々に考えることによって意味のある因数分解を定めることができる。 自然数および整数に関する因数分解は古代ギリシアのにおいてすでに考察されている。その中には、１を除く任意の自然数が素数の積に因数分解できる（さらに、自然数のそのような分解（素因数分解）は因数の順番を変える違いを除いて一通りである）ことを述べた算術の基本定理の証明も含まれる。整数の素因数分解は、整数の乗法のある種の逆演算ではあるけれども、しかしアルゴリズム的な意味（計算量）において乗法とは比べ物にならないほど複雑であり、特に巨大整数の素因数分解は困難な問題で、これを一般に短時間に行う方法は知られていない。この複雑性はRSA暗号のような公開鍵暗号によるセキュリティの信頼性の基礎になっている。 多項式の因数分解もまた何世紀にもわたって研究がおこなわれてきている。初等代数学においては、多項式を因数分解することで多項式の根を求める求根問題を各因子の根を求める問題に帰着させることができる。整数係数の多項式あるいは体に係数をとる多項式の体系は一意分解性質を備えている—それはつまり、（素数を既約多項式に取り換えた）算術の基本定理の多項式版が成り立つということである—。特に、複素数係数の一変数多項式は、必ずの積に（掛ける順番を除いて）一意に表すことができる—これは代数学の基本定理の一つの述べ方である—。この場合、因数分解は求根アルゴリズムが与えられていれば自由にできる。整数係数の場合の多項式の因数分解問題は計算機代数においてひとつの基礎を成す技術的課題である。有理数係数の多項式環における既約因子分解には、効果的な計算機アルゴリズムが存在している。 一般の抽象代数学において、一意分解性質を持つ可換環は一意分解環 (UFD) と呼ばれる。ある種の、例えば代数体の整数環（代数的整数環）の中には一意分解性質を持たないものが存在するが、これら代数的整数環の場合には幸いなことに、より弱い形での一意分解性質（任意のイデアルが素イデアルの積に一意的に分解される）を満足するデデキント環となる。一般に、既約元分解を持つ（が、一意分解とは限らない）整域をまたは分解整域と呼ぶ。 より一般の数学的対象の中にも（より単純な対象からなる）積の形に書き表すことを一般に因子分解あるいは分解と言い表すものがある。たとえば、写像の分解とは特定の性質を持つ写像の合成の形に書き表すことである。任意の写像は全射と単射の合成として標準的な分解を持つ（これは圏論において、射のとして一般化される）。また例えば、行列の分解とは、与えられた行列を特定の性質を持つ行列を用いて行列の積として書き表すことである。任意の行列は対角成分がすべて 1 の下三角行列 L と上三角行列 U および 置換行列 P の積に分解される（LUP分解: 実はこれはガウスの消去法を行列の形にまとめたものである）。