多項式の因数分解
因数分解にも（本当は）いろいろあるのですが、今回は1変数整数係数多項式を、定数でない1変数整数係数多項式の積で書くことを考えます。若干表現が遠回りかもしれませんが、いわゆる普通の因数分解です。
さて、コンピュータで因数分解をするにはどうすればいいでしょうか。
直接因数分解するのは難しそうなので、因子の候補をすべて挙げて、その中から適しているものを選べばよさそうです。
問題はその因子の候補の選び方ですね。因子の候補はモレがあってはいけませんし、できることなら候補の数は減らしたいわけです（候補の数が多いと、適しているかどうかのチェックに時間がかかってしまいます）。
効率のいいアルゴリズムとかだと環論とかの知識を使うらしいんですが、残念ながらそういう抽象代数学の知識がないので、今回は頭の悪い方法で計算量的にはかなり効率が悪いのですが、単純な方法で因数分解してみたいと思います。
アルゴリズムの主要部分
今回紹介するのはKroneckerの方法（Wikipedia(英語)）です。原理はわりと単純なので理解しやすいと思います。
英語版wikipediaを読むのが一番手っ取り早いと思いますが、英語なんて読めねぇぜって人もいると思うので要点だけかいつまんで説明すると、因数分解したい多項式の整数での値の約数を調べて、約数の全組み合わせに対して多項式を調べて因子を決定する、というものです。
ところがこの方法、たった5次の多項式を因数分解するのにも、128通り（英語版wikipediaには実質64通りって書いてありますが組み合わせだけからどうやって高速に見分けるんでしょうねぇ）調べなければならず、結構大変です。
みたいなわりと単純な多項式を因数分解する場合でも、約100兆通りも調べなければならなくて、こんなのは現代のPCではめちゃくちゃ計算時間がかかってやってられないわけです。
そこでいろいろ工夫をして処理量を減らすわけですね。
工夫その1
Kroneckerのアルゴリズムの欠点は、因数分解したあとの因数の数（重複度も含めて考えます）が増えると、約数の数も当然増えて、組み合わせが膨大になってしまう点です。
そこで、Kroneckerのアルゴリズムに頼らなくても（完全なとはいわないけど）因数分解できるところについては分解してしまえば、因数分解する多項式の数は増えますがそれよりも組み合わせ爆発を抑える効果のほうが圧倒的に大きくなり、因数分解が高速化されます。
ここで登場するのが無平方分解です。
無平方分解というのは、多項式を因数分解したときにの部分が現れないようにすることです。
一見実行が難しそうですが、かなり単純なアルゴリズムで計算できます。
多項式を微分したものと元の多項式の最大公約数（最大公約多項式といったほうがわかりやすいかも）をとると、多項式を因数分解したときのの部分が
になって出てきます。
従って
を計算すれば、重複度がちょうどの因子が出てくるわけです。
多項式の微分は普通に各項ごとに微分すればいいですし、多項式の最大公約数はユークリッドの互除法と同じアルゴリズムで計算できます。
これにより、因子の数を減らして計算を高速化できるようになるばかりか、最終的に出てきた候補のうち次数が小さいものから順に割っていって割り切れたら商をもとの多項式として試行除算を繰り返す、という操作だけで因子の規約性も保証されながらすべて求められるというオマケ付きです。
工夫その2
先のような工夫は平方因子を持つ多項式に対しては非常に有効なのですが、先ほどののように平方因子をもたない多項式に対しては完全に無力です。
では、平方因子を持たない多項式に対して打つ手はないのでしょうか？
いいえ、あります。うまく枝刈りをすればいいわけです。
合同式の性質として、任意の整数係数多項式に対して、ならば
が成り立つというものがありましたね（合同式の法はなんでもいいです）。つまり、整数係数多項式なら
は
で割りきれます。ということは、
が
の倍数でないような
が存在するなら、その約数の組み合わせは整数係数多項式を生成しないので不適ということがわかります。
これは整数列が整数係数多項式を生成するための必要十分条件ではない（例えば～
がそれぞれ1,1,1,1,13のとき、
は整数係数じゃないのに
は
で割りきれる）ですが、反例となる多項式の数はかなり少なく、また整数列の途中までしか見なくても整数係数多項式にはならないということがわかるので非常に有効な枝刈り法です。
