Pollard Rho 实施有什么问题

Question

#include <iostream>
#include <cstdlib>
typedef  unsigned long long int ULL;
ULL gcd(ULL a, ULL b)
{
   for(; b >0 ;)
   {
       ULL rem = a % b;
       a = b;
       b = rem;
   }
   return a;
}
void pollard_rho(ULL n)
{
   ULL i = 0,y,k,d;
   ULL *x = new ULL[2*n];
   x[0] = rand() % n;
   y = x[0];
   k = 2;
   while(1){
       i = i+1;
       std::cout << x[i-1];
       x[i] = (x[i-1]*x[i-1]-1)%n;
       d = gcd(abs(y - x[i]),n);
       if(d!= 1 && d!=n)
          std::cout <<d<<std::endl;
       if(i+1==k){
         y = x[i];
         k = 2*k;
       }
   }
}

int main()
{
   srand(time(NULL));
   pollard_rho(10);

}

该实现源自 CLRS 第二版（页码 894）。 while(1) 对我来说看起来很可疑。 while 循环的终止条件应该是什么？

我尝试了 k<=n 但这似乎不起作用。我遇到分段错误。代码中有什么缺陷以及如何纠正它？

Answer 1

我只有 CLRS 第一版，但假设它与第二版没有太大不同，终止条件的答案在下一页：

这个寻找因子的过程乍一看可能有些神秘。但请注意，POLLARD-RHO 永远不会打印错误的答案；它打印的任何数字都是 n 的非平凡除数。不过，POLLARD-RHO 可能根本不会打印任何内容；无法保证它会产生任何结果。然而，我们将看到，有充分的理由期望 POLLARD-RHO 在大约 sqrt(p ) while 循环的迭代。因此，如果n是合数，我们可以期望这个过程在大约n^{1/4之后发现足够的除数来完全分解n} 更新，因为 n 的每个质因数 p（可能除了最大的一个）都小于 sqrt(n)。

因此，从技术上讲，CLRS 中的演示文稿没有终止条件（这可能就是为什么他们称其为“启发式”和“过程”而不是“算法”），并且不能保证它实际上会产生任何内容有用。实际上，您可能希望根据预期的 n^1/4 更新设置一些迭代限制。

Answer 2

为什么要存储所有这些中间值？您确实不需要将 x 和 y 放入数组中。只需使用您不断重复使用的 2 个变量：x 和 y。

另外，将 while(1) 替换为 while(d == 1) 并在之前切断循环。

 if(d!= 1 && d!=n)
      std::cout <<d<<std::endl;
   if(i+1==k){
     y = x[i];
     k = 2*k;

您的循环应该成为

while(d == 1)
{
    x = (x*x - 1) % n;
    y = (y*y - 1) % n;
    y = (y*y - 1) % n;
    d = abs(gcd(y-x,n))%n;
}
if(d!=n)
  std::cout <<d<<std::endl;
else
  std::cout<<"Can't find result with this function \n";

因此，如果您传递循环内使用的函数， 额外的分数作为 pollard 的参数，这样如果它无法用一个函数找到结果，它就会尝试另一个函数。

Answer 3

尝试将 while(1) { i = i + 1; 替换为：

for (i = 1; i < 2*n; ++i) {