MBPSによる因数分解
2006/06/06 早稲田大学 後 保範 (Waseda University, Ushiro Yasunori )
2006/10/29 改訂(MBPS2への拡張アイデアを追記)
0. はじめに
2006年1月に独自に考案したPS(多項式篩法)を発展させた方式である。
MBPSはMultiple Base Polynomial Sieveの略で、多重基底多項式篩法と言う。
まだ、GNFSとの比較のための計算量の評価は完了していない。
MBPSはPSと同様に2〜4次の多項式に適用でき、GNFSと合体して利用可能である。
本MBPSの最大の特長は、篩に一次式基底を導入し、一次式基底による分解はGNFS(一般数体篩法)
の素イデアルでの分解と異なり、自然に求まることである。また、左辺と右辺に現われる一次式は
共に一次式基底で処理できる。更に、左辺側の一次式は同一なものが多量に出現する。この性質に
より、多数桁数の因数分解でGNFSより高速化できると思われる。
1. MBPSの各種方式
MBPSの考えはMBPS2(改訂多重基底多項式ふるい法)に受け継ぎ、発展させています。
MPPS2を参照してください。
MBPSからMBPS2に拡張するするために追加した主なアイデアは下記の点です。
(a) イデアルの概念を使用し、乗算する一次式を選定する。
これにより、sx+tが同一でGが異なるものを集めるふるいの効率を向上させる
--> MBPS2(改訂多重基底多項式ふるい法)
(1) NAS2006予稿 |
(2) NAS2006発表資料 |
(3) ゼミ勉強会資料(MBPS)