MBPSによる因数分解のプログラム

    2006/05/25 早稲田大学 後 保範 (Waseda University, Ushiro Yasunori )

0. はじめに

  2006年1月に独自に考案したPS(多項式篩法)を発展させた方式である。
 MBPSはMultiple Base Polynomial Sieveの略で、多重基底多項式篩法と言う。
 まだ、GNFSとの比較のための計算量の評価は完了していない。
 MBPSはPSと同様に2〜4次の多項式に適用でき、GNFSと合体して利用可能である。
 本MBPSの最大の特長は、篩に一次式基底を導入し、一次式基底による分解はGNFS(一般数体篩法)
 の素イデアルでの分解と異なり、自然に求まることである。また、左辺と右辺に現われる一次式は
 共に一次式基底で処理できる。更に、左辺側の一次式は同一なものが多量に出現する。この性質に
 より、多数桁数の因数分解でGNFSより高速化できると思われる。

2. MBPS(2次多項式)による篩プログラム

3. MBPS(3次多項式)による篩プログラム

4. MBPS(4次多項式)による篩プログラム

5. MBPS(2次多項式でGNFSと合体)による篩プログラム