c++ - 这个 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 第 2 版(页码 894)。 while(1)在我看来很可疑。 while 循环的终止条件应该是什么？

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

Answer 1

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

This procedure for finding a factor may seem somewhat mysterious at first. Note, however, that POLLARD-RHO never prints an incorrect answer; any number it prints is a nontrivial divisor of n. POLLARD-RHO may not print anything at all, though; there is no guarantee that it will produce any results. We shall see, however, that there is good reason to expect POLLARD-RHO to print a factor of p of n after approximately sqrt(p) iterations of the while loop. Thus, if n is composite, we can expect this procedure to discover enough divisors to factor n completely after approximately n^1/4 update, since every prime factor p of n except possibly the largest one is less than sqrt(n).

因此，从技术上讲，CLRS 中的表示没有终止条件(这可能就是为什么他们将其称为“启发式”和“过程”而不是“算法”的原因)并且无法保证它永远不会实际上产生任何有用的东西。在实践中，您可能希望根据预期的 n^1/4 更新来限制一些迭代。