| 快速分解法 |
| 位置 主页
-> 初等数论 |
|
p[i] 表示第i小的素数 |
| p-1 法 |
|
x=3;
i=1;
while
(enough>i) {
x=x^p[i] mod N;
G=gcd(x-1,N);
if N>G>1 then {
print(G);
N=N/G;
}
i++
}
|
| ρ 法 |
|
A=2;
B=A;
while
(enough>i) {
A=(A^2+1) mod N;
B=((B^2+1)^2+1) mod N;
G=gcd(B-A, N);
if N>G>1 then {
print(G);
N=N/G;
}
i++
}
|
|
|
|
|
|
|
| 椭圆曲线法(ECM) |
|
|
| 连分数法 () |
|
|
| 二次筛法(QS) |
|
|
| 其它 |
|
这些是没有找到资料的分解法:
数域筛选法(NFS 有 SNFS, GNFS) |
|
|