爆発は男のロマンだ！（ガミガミ魔王）
エクスプロージョン！（めぐみん）
というわけで、爆発させて／してみました。
多項式の因数分解、まだやっていたのです。話は終わってないのです。因数分解出来るテストデータはよいのですが（実はよくない）、因数分解できない場合つまり既約多項式の場合、どうするかという問題があった。つまり既約判定ですね。元のアルゴリズムでは(p^d-1)/2 回くらい多項式をべき乗して、それでも割れなければ既約という判定になっていたのですが、(p^d-1)/2 回もべき乗するのは嫌だということで取ってしまったのでした。それだと既約と判定できないのである。
ここで考えを変えて、あらかじめ既約多項式を求めておけばよいのではないか思ったのである。前もって計算しておくのは計算量ゼロじゃないか。これはお得だ。素因数分解だってエラトステネスの篩というのがあるし、それの多項式版をやればいいじゃないかと。もちろん、メモリなりディスク容量なりを消費するのは分かっていたが、まあメモリは昔のコンピュータに比べたら大量にあるし……。
ja.wikipedia.org前もって計算した既約多項式
閲覧注意。なかなかに爆発してます。いや、リンク先は単にデータへのリンクリストだけど、その先の実際のデータが多い。
