多項式の因数分解
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次より上で数千ディジットの係数を持つ場合でも整係数一変数多項式を素早く因数分解することができる。
整係数多項式の場合と同様に、この場合も、有理係数多項式を有理数と整係数原始多項式の積への分解が、符号のとり方を除いて一意に定義される。
カール・フリードリヒ・ガウスは二つの原始多項式の積がふたたび原始的であること(ガウスの補題(英語版))を示した。これにより「原始多項式が有理数体上既約であるための必要十分条件は、整数環上で既約であること」が従う。これはつまり、有理係数多項式の有理数体上での因数分解が、その原始成分の整数環上での因数分解と同じことであることをも意味する。他方、整係数多項式の整数環上での因数分解は、その原始成分の分解と内容の素因数分解とを掛けることで与えられる。
言い方を変えれば、整数のGCD計算によって有理係数多項式の因数分解は整係数原始多項式の因数分解に帰着され、また整数環上での因数分解は整数の因数分解と原始多項式の因数分解に帰着することができるようになるということである。
さてここまでに述べたことは、Z を体 F 上の多項式環で、および Q を F の有理函数体でそれぞれ置き換えて(ただし置き換え後の両者の不定元は共通とする)、「符号の違いを除いて」という代わりに「F の単元を掛ける違いを除いて」とすれば、すべてそのまま成り立つ。この場合、F の純超越拡大体上での因数分解が F 上の多変数多項式の因数分解に帰着される。
本節では、有理数体 Q 上での因数分解は整数環 Z 上での因数分解と本質的に同じ問題であることを示す。
整係数多項式 p ∈ Z[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 のそれで、それぞれ定義する。