大整数分解pollard（注意2^59次方分解不了）

void Pollard(long long n);
void Factor(long long n) {
long long d = 2;
while (true) {
if (n % d == 0) {
Pollard(d);
Pollard(n / d);
return;
}
d++;
}
}
void Pollard(long long n) {
if (n <= 0)
printf("error\n");
if (n == 1)
return;
if (Miller_rabin(n)) {
factor[cnt++] = n;
return;
}
long long i = 0, k = 2, x, y, d;
x = y = rand() % (n - 1) + 1;
while (i++ < 123456) {
x = (Mul_Mod(x, x, n) + n - 1) % n;
d = Gcd((y - x + n) % n, n);
if (d != 1) {
Pollard(d);
Pollard(n / d);
return;
}
if (i == k) {
y = x;
k *= 2;
}
}
Factor(n);
}

本文出自 “Qero” 博客，请务必保留此出处http://8590696.blog.51cto.com/8580696/1358927

大整数分解pollard（注意2^59次方分解不了）

原文：http://8590696.blog.51cto.com/8580696/1358927