多項式たこうしきの因数いんすう分解ぶんかい

数学すうがくおよび計算けいさん機き代数だいすうにおける多項式たこうしきの因数いんすう分解ぶんかい（いんすうぶんかい、英えい: 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