另一个 Pollard Rho 实现
Another Pollard Rho Implementation
为了解决项目 Euler (https://projecteuler.net/problem=3) 的第三个问题,我决定实施 Pollard 的 Rho 算法(至少是其中的一部分,我计划稍后包括循环)。奇怪的是它适用于以下数字:82123(因子 = 41)和 16843009(因子 257)。然而,当我尝试项目欧拉数:600851475143 时,当最大质因数为 6857 时,我最终得到 71。这是我的实现(对于代码墙和缺乏类型转换感到抱歉):
#include <iostream>
#include <math.h>
#include <vector>
using namespace std;
long long int gcd(long long int a,long long int b);
long long int f(long long int x);
int main()
{
long long int i, x, y, N, factor, iterations = 0, counter = 0;
vector<long long int>factors;
factor = 1;
x = 631;
N = 600851475143;
factors.push_back(x);
while (factor == 1)
{
y = f(x);
y = y % N;
factors.push_back(y);
cout << "\niteration" << iterations << ":\t";
i = 0;
while (factor == 1 && (i < factors.size() - 1))
{
factor = gcd(abs(factors.back() - factors[i]), N);
cout << factor << " ";
i++;
}
x = y;
//factor = 2;
iterations++;
}
system("PAUSE");
return 0;
}
long long int gcd(long long int a, long long int b)
{
long long int remainder;
do
{
remainder = a % b;
a = b;
b = remainder;
} while (remainder != 0);
return a;
}
long long int f(long long int x)
{
//x = x*x * 1024 + 32767;
x = x*x + 1;
return x;
}
Pollard 的 rho 算法不提供任何保证。它不能保证找到最大的因素。它不保证它找到的任何因子都是质数。它甚至不能保证找到一个因素。 rho 算法是概率性的;它可能会找到一个因素,但不一定。由于你的函数 returns 是一个因子,所以它有效。
也就是说,您的实现不是很好。没有必要存储函数的所有先前值,并在每次循环中计算 gcd。这是该函数更好版本的伪代码:
function rho(n)
for c from 1 to infinity
h, t := 1, 1
repeat
h := (h*h+c) % n # the hare runs ...
h := (h*h+c) % n # ... twice as fast
t := (t*t+c) % n # as the tortoise
g := gcd(t-h, n)
while g == 1
if g < n then return g
此函数returns n 的单个因子,可以是素数或合数。它仅存储随机序列的两个值,并在找到循环时停止(当 g == n 时),并以不同的随机序列重新启动(通过递增 c)。否则它会一直运行直到找到一个因子,只要您将输入限制为 64 位整数,它就不会花费太长时间。通过将 rho 应用于剩余的辅助因子来查找更多因子,或者如果找到的因子是复合因子,则在找到所有主要因子后停止。
顺便说一下,您不需要 Pollard 的 rho 算法来解决欧拉计划 #3;简单的试验划分就足够了。该算法找出一个数的所有质因数,从中可以提取最大的:
function factors(n)
f := 2
while f * f <= n
while n % f == 0
print f
n := n / f
f := f + 1
if n > 1 then print n
为了解决项目 Euler (https://projecteuler.net/problem=3) 的第三个问题,我决定实施 Pollard 的 Rho 算法(至少是其中的一部分,我计划稍后包括循环)。奇怪的是它适用于以下数字:82123(因子 = 41)和 16843009(因子 257)。然而,当我尝试项目欧拉数:600851475143 时,当最大质因数为 6857 时,我最终得到 71。这是我的实现(对于代码墙和缺乏类型转换感到抱歉):
#include <iostream>
#include <math.h>
#include <vector>
using namespace std;
long long int gcd(long long int a,long long int b);
long long int f(long long int x);
int main()
{
long long int i, x, y, N, factor, iterations = 0, counter = 0;
vector<long long int>factors;
factor = 1;
x = 631;
N = 600851475143;
factors.push_back(x);
while (factor == 1)
{
y = f(x);
y = y % N;
factors.push_back(y);
cout << "\niteration" << iterations << ":\t";
i = 0;
while (factor == 1 && (i < factors.size() - 1))
{
factor = gcd(abs(factors.back() - factors[i]), N);
cout << factor << " ";
i++;
}
x = y;
//factor = 2;
iterations++;
}
system("PAUSE");
return 0;
}
long long int gcd(long long int a, long long int b)
{
long long int remainder;
do
{
remainder = a % b;
a = b;
b = remainder;
} while (remainder != 0);
return a;
}
long long int f(long long int x)
{
//x = x*x * 1024 + 32767;
x = x*x + 1;
return x;
}
Pollard 的 rho 算法不提供任何保证。它不能保证找到最大的因素。它不保证它找到的任何因子都是质数。它甚至不能保证找到一个因素。 rho 算法是概率性的;它可能会找到一个因素,但不一定。由于你的函数 returns 是一个因子,所以它有效。
也就是说,您的实现不是很好。没有必要存储函数的所有先前值,并在每次循环中计算 gcd。这是该函数更好版本的伪代码:
function rho(n)
for c from 1 to infinity
h, t := 1, 1
repeat
h := (h*h+c) % n # the hare runs ...
h := (h*h+c) % n # ... twice as fast
t := (t*t+c) % n # as the tortoise
g := gcd(t-h, n)
while g == 1
if g < n then return g
此函数returns n 的单个因子,可以是素数或合数。它仅存储随机序列的两个值,并在找到循环时停止(当 g == n 时),并以不同的随机序列重新启动(通过递增 c)。否则它会一直运行直到找到一个因子,只要您将输入限制为 64 位整数,它就不会花费太长时间。通过将 rho 应用于剩余的辅助因子来查找更多因子,或者如果找到的因子是复合因子,则在找到所有主要因子后停止。
顺便说一下,您不需要 Pollard 的 rho 算法来解决欧拉计划 #3;简单的试验划分就足够了。该算法找出一个数的所有质因数,从中可以提取最大的:
function factors(n)
f := 2
while f * f <= n
while n % f == 0
print f
n := n / f
f := f + 1
if n > 1 then print n