自分のバグを修正していく過程で、Cantor–Zassenhausのアルゴリズムの弱点が分かってきたような気がする。
まず、「因数分解は素因数分解よりやさしい」とかこのブログに書いたけど、大嘘でした。計算量としても特に優れているとは言えない。そもそも俺のプログラムでは素因数分解してるし。素因数分解を使っているのに、それよりやさしいということはない。
有限体上での多項式の分解はそこそこ効率的であるが、これが結構失敗する。ヘンゼル持ち上げは、前提条件を満たさない。
その理由をよくよく頭をしぼって考えてみると、与えられた多項式（これから因数分解する多項式）が、多くの1次式の積となっている場合に、有限体上の環が多くの小さな部分に分かれるというのが原因のようだ。プログラムテスト用のデータがまさにそういう多項式であったので、問題が発覚した。
特に問題なのは、ランダムに選んだ多項式を、情報群の位数の半分だけべき乗するというところ。半分は良くないだろう。元に戻る可能性が高い。位数の半分近くの、位数と素な数だけべき乗するのがよい。いや、位数の3分の1とかの方がよいかも。
ヘンゼル持ち上げも、因子が多い時は前提条件を満たさないことが多いのだが、俺は勘違いしていて、ヘンゼル持ち上げが前提条件を満たさない時は、最初からやり直していた。これは大間違いで、そこだけスキップすればよいはず。それをやるとことごとくスキップしてしまうこともあるようだ。その時はpを変えてやり直し。このように泥臭い。
そしてヘンゼル持ち上げはp^nの世界の話で、そこから整数の世界に来るためには、最高次の係数を決めなければならない。ここで素因数分解を使いましたよ。そしてどうせ素因数分解を使うならと、mod p でも mod p^n でも最高次の係数は1にしておいた。
これでもまだ時々因数分解に失敗する。
ただ、原因はほぼ上に書いたようなこと。つまり、1次式の多さだと思うので、もう1番最初の処理として、高校生がやるような代入法を使って1次式をいくつか取り除いておこうかと考えている。あと無平方分解も1次式なら取ってしまおうか。こうやって少しでも1次式を減らす。
あとは、出てきた因数分解の結果について、1次式でなければもう一度因数分解のアルゴリズムを適用するとかだろうか。泥臭い上に、もう1度やったからといってうまく行く保証もない。
それとも、俺の理解が根本的に間違っているのだろうか？
