MBPS2による因数分解のプログラム
2006/08/18 後 保範 ( Ushiro Yasunori )
0. はじめに
MBPS(Multiple Base Polynomial Sieve、多重基底多項式篩法)の改良版である。
MBPS2はMultiple Base Polynomial Sieve 2ndの略で、改訂多重基底多項式篩法と言う。
MBPS(多重基底多項式篩法)に対して、多項式f(x)を法とし、素イデアル基底で分解できるイデアルの積
で作られるイデアルも素イデアル基底で分解できる、特長を利用した方法。
この性質のため、f(x)=Ax2+Bx+Cに対して、Sx+T=(Ax+a)(x+b)-f(x)とすると、Ax+a及びx+b
が素イデアル基底で分解できると、Sx+Tも素イデアル基底で分解できる。
AM+a及びM+bは素数基底でも分解可能なものを選ぶ(逆にこれを分解する素数を素数基底に入れる)と
(AM+a)(M+b)=SM+T (mod f(M)=N)で(AM+a)(M+b)は素数基底で分解でき、更にSx+Tは素イデアル基底で分解
できる。即ち、ふるいで得られた等式となる。ここで、Nは分解対象数である。
ここで、非常に嬉しいのはAx+aをm1個、x+bをm2個用いると、Sx+Tはm1・m2個作成される。そのため、
ふるいで得られる等式の数が、素数基底と素イデアル基底の合計数を容易に超えることが可能となる。
現在、f(x)は2次多項式及び3次多項式の適用が可能である。
MBPS単独で使用する場合DBPS2(Double Base Polynomial Sieve 2nd、改訂2重基底多項式篩法)と言う。
GNFSと合体し使用する場合TBPS2(Triple Base Polynomial Sieve 2nd、改訂3重基底多項式篩法)と言う。
1. DBPS2(2次多項式)による篩プログラム
2. DBPS2(3次多項式)による篩プログラム
3. TBPS2(2次多項式でGNFSと合体)による篩プログラム