MBPS2による因数分解具体例

　　　　2006/08/18 後保範 ( Ushiro Yasunori )
　　　　2006/11/09 追加・改訂 (2次方程式のDBPS2)

0. はじめに

　　MBPS(Multiple Base Polynomial Sieve、多重基底多項式篩法)の改良版である。
　MBPS2はMultiple Base Polynomial Sieve 2ndの略で、改訂多重基底多項式篩法と言う。
　MBPS(多重基底多項式篩法)に対して、多項式f(x)を法とし、素イデアル基底で分解できるイデアルの積
　で作られるイデアルも素イデアル基底で分解できる、特長を利用した方法。
　この性質のため、f(x)=Ax²+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による篩の具体例

　(1) 2次多項式によるふるい例1
　(2) 2次多項式によるふるい例2
　(3) 3次多項式によるふるい例

2. DBPS2による因数分解の具体例

　(1) 2次多項式による因数分解例1
　(2) 2次多項式による因数分解例2
　(3) 3次多項式による因数分解例

3. TBPS2による篩の具体例

　(1) 2次多項式によるふるい例
　(2) 3次多項式によるふるい例

4. TBPS2による因数分解の具体例

　(1) 2次多項式による因数分解例
　(2) 3次多項式による因数分解例