c++ - 此Pollard Rho实现有什么问题

#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，但似乎不起作用。我遇到细分错误。代码中的缺陷是什么？如何纠正？

最佳答案

我只有CLRS的第一版，但是假设它与第二版没有太大差异，终止条件的答案在下一页:



因此，从技术上讲，CLRS中的演示文稿没有终止条件(这可能就是为什么他们将其称为“启发式”和“过程”而不是“算法”的原因)，并且不能保证它会真正产生任何结果有用。实际上，您可能希望基于预期的n1 / 4更新来放置一些迭代边界。

关于c++ - 此Pollard Rho实现有什么问题，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6040423/