MBPSによる因数分解のプログラム
2006/05/25 後 保範 ( 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と合体)による篩プログラム