| 項 目 | MBPS2 | PS | GNFS | MPQS | |
| 小項目 | DBPS2 | TBPS2 | --- | --- | --- |
| 100桁以上でふるい採用率 | 大 | ほぼ100% | 小 | 小 | 極めて小 |
| 使用多項式 | 2〜4次式 | 2〜4次式 | 2〜4次式 | 3〜7次式 | 2次式 |
| 使用方程式数 | 1個又は複数 | 1個又は複数 | 複数 | 1個 | 多数 |
| 片方が平方数 | 利用しない | 不成立 | 変形し成立 | 不成立 | 成立 |
| イデアルの使用 | 限定利用 | 利用 | 利用しない | 利用 | 利用しない |
| 代数平方根の計算 | 不要 | 必須 | 不要 | 必須 | 不要 |
| 篩分解部分の等式 | 成立 | 不成立 | 成立 | 不成立 | 成立 |
| 計算式(2又は3次式) (nは分解対象数) |
f(x)=Ax2+Bx+C f(M)=0 (mod n) (Ax+a)(x+b)-f(x)=sx+t s=a+Ab-b, t=ab-C v=sign(s)GCD(|s|,|t|) S=t/v, T=t/v |
同左 | f(x)=Ax3+Bx3+Cx+D f(M)=0 (mod n) |
f(x)=((ax+b)2-n)/a =ax2+Bx+C B=2b, C=(b2-n)/a |
|
| 一次式及びイデアル の選定 |
指定範囲の整数a,bに対し Aθ+a,θ+bが素イデアル基底 で分解できるものを選ぶ。 ここで、AM+a,M+bは分解で きるように素数基底を追加 |
指定範囲の整数 a,bでAM+a,M+b を総て選ぶ。 |
指定範囲の整数 a,bに対して下記 整数：aM+b イデアル：aθ+b |
指定範囲の整数 xに対してf(x) |
|
| ふるい | S,Tが同じで vが異なる ものを採択 |
総て採択し 重複データ なら除く |
S,Tが同じで vが異なる ものを採択 |
aM+bとaθ+bが共 に対応基底で分解 できるデータ |
F(x)が素数基底で 分解できるデータ |
| 採択向上策 | 同右の原理が 同じS,Tの比 率向上を招く |
素イデアル基底 で分解できる イデアルの積は また分解できる |
- - - | - - - | - - - |
| 計算係数(p) | < 1/3 ? | < 1/3 ? | 1/3 ? | 1/3 | 1/2 |