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