PSによる因数分解
2006/03/20 早稲田大学 後 保範 (Waseda University, Ushiro Yasunori )
2006/10/29 改訂(MBPS2への拡張アイデアを追記)
0. はじめに
2006年1月に独自に考案した方式である。GNFSの改善ができないか検討していて発見した。
まだ、GNFSとの比較のための計算量の評価は完了していない。
PS(多項式篩法)は2〜4次の多項式に適用でき、GNFSと合体して利用可能である。
現在、3次多項式篩法(P3S)とGNFSを合体したプログラムを多数桁因数分解の世界記録達成に向けて
作成中である。
PSの特色は2〜4次多項式に適用できるために、MPQS(複数多項式2次篩法)の限界(分解関数値の
大きさが分解対象数の平方以下にできない)を突破した点である。また、3次以上の多項式を使用
すると、分解対象多項式以外に発生する一次式(GNFSでは素数基底での分解が必要)に同じものが
多数発生するため、素数基底での分解がほとんど必要なくなる利点がある。
2次多項式篩法(P2S)では一次式側に同じものを発生させる方法が現在判明していない。そのため
1次式の素数基底による分解の計算量が大きく、実用にならない。ただし、一次式側に共通因子
を発生させる方法が分かれば、3〜4次式より高速になり得る。また、4次式の効率的利用について
研究中である。
GNFSは多項式の次数に関係なく一般的な方法が得られるが、PSは次数毎に異なり、2次、3次、
多項式に適用するものをそれぞれP2S,P3S,P4Sと名付ける。
1. PSの基本原理
PSの考えはMBPS2(改訂多重基底多項式ふるい法)に受け継ぎ、発展させています。
MPPS2を参照してください。
PSからMBPS2に拡張するするために追加した主なアイデアは下記の2点です。
(1) 得られた1次式Sx+TのSとTの共通因子(GCD(S,T))をGとし、SX+T=G(sx+t)と変形し、sx+tが同一で
Gが異なるものをふるいで集める。--> MBPS(多重基底多項式ふるい法)
(2) イデアルの概念を使用し、乗算する一次式を選定する。
これにより、sx+tが同一でGが異なるものを集めるふるいの効率を向上させる
--> MBPS2(改訂多重基底多項式ふるい法)
2. PSの各種方式
(1) P2S(2次多項式篩法) --> DBPS2(2次多項式の改訂2重基底多項式ふるい法)に拡張
(2) P3S(3次多項式篩法) --> DBPS2(3次多項式の改訂2重基底多項式ふるい法)に拡張
(3) P3NFS(2次多項式篩とGNFSの合体) --> TBPS2(2次多項式の改訂3重基底多項式ふるい法)に拡張
(4) P3NFS(3次多項式篩とGNFSの合体) --> TBPS2(3次多項式の改訂3重基底多項式ふるい法)に拡張