追記:以下は間違い。プログラムを作ってみた結果、全然やさしくなかった。計算量的にもそんなによくない。
高校までの数学と大学の数学で難しさが逆転する例かも。
なんか、整数では難しい問題も多項式なら簡単になるという例がいくつかあるらしい。その一つが整数の素因数分解と多項式の因数分解だという。
少し前に(年寄りの少し前なので、若い人にはずいぶん前)、三角関数は難しいとか要らないとかいう話題があったが、三角関数と並んで難しいのが因数分解である。三角関数で挫折した人と同じくらい因数分解でつまずいた人がいるらしい。
それも当然というか、高校で習う因数分解はいくつかの公式を適切に選んで当てはめるという、なかなかヒューリスティックというかアドホックというかパズル的な手法で頭を捻って解くことになっている。つまりは、鶴亀算を方程式を使わずに解いているようなものである。解の公式を使うことも出来るが、それも4次方程式までしか使えない。(それに、3次以上の解の公式を使うのは知恵は絞らないにしても、すごく面倒くさい)。多変数の多項式でも解の公式は使えない。
じゃあ、鶴亀算の代わりに方程式を使うような決まった手順による因数分解の仕方はないのかというと、あるのである。
難しいこと書いてあるけど、なあにアルゴリズムがあるなら、プログラムになっているので、そのプログラムを使えばいい。
Mathematica を起動して Factor を使えばいいのである。終了。
reference.wolfram.com近ごろ流行の python というやつでも SymPy とかいうパッケージを使うと因数分解が出来るらしい。sympy.factor
python.atelierkobato.comまあ、貧乏人の俺はMaxima を使うけど。
因数分解のアルゴリズムを詳しく知りたい人は、まず大学の代数の勉強をして環とか有限体について学ぼう。代数をやれば、大数学者にはなれなくても、代数学者にはなれる。