其他Pollard Rho实施

Question

试图解决Euler项目的第三个问题（Https：//projecteuler.net/problem =3），我决定实现Pollard的Rho算法（至少一部分，我计划在其中包括循环循环之后）。奇怪的是，它适用于：82123（因子= 41）和16843009（因子257）等数字。但是，当我尝试该项目Euler编号：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;
}

Answer 1

帕拉德的Rho算法一无所获。它不能保证找到最大的因素。它不能保证其发现的任何因素都是主要的。它甚至不能保证找到一个因素。 Rho算法是概率的；它可能会找到一个因素，但不一定是。由于您的功能返回一个因素，因此起作用。

说，您的实施不是很好。不必存储函数的所有先前值，并每次通过循环计算到每个函数。这是一个更好版本的函数版本的伪代码：

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

该函数返回一个n的单个因子，这可能是素数或复合材料。它仅存储随机序列的两个值，并在找到一个循环时停止（当g == n），以不同的随机序列（通过递增C）重新启动。否则，它会一直进行，直到找到一个因素为止，只要您将输入限制为64位整数，就不应花费太长时间。通过将RHO应用于剩余的辅助因子，或者如果发现所有主要因素时停止，找到更多因素。

顺便说一句，您不需要Pollard的Rho算法来解决Euler＃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

在这里是Pollard的Rho算法的实现。

Answer 2

知道该算法找不到完美的功能，并且在给出素数时不会停止。