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)