1 
#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ましたが、うまくいかないようです。セグメンテーション違反が発生します。コードの欠陥とその修正方法は何ですか？

4

3 に答える 3

1

これらすべての中間値を保存するのはなぜですか? x と y を配列に入れる必要はありません。x再利用し続ける2つの変数を使用するだけです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が得られます。これにより、1 つの関数で結果が見つからない場合、別の関数が試行されます。

于 2011-05-18T06:32:14.427 に答える
1

私は CLRS の第 1 版しか持っていませんが、第 2 版とあまり変わらないと仮定すると、終了条件の答えは次のページにあります。

因数を見つけるためのこの手順は、最初はやや不可解に思えるかもしれません。ただし、POLLARD-RHO は間違った答えを表示しないことに注意してください。出力される数値は、 nの非自明な除数です。ただし、POLLARD-RHO は何も印刷しない場合があります。何らかの結果が得られるという保証はありません。ただし、POLLARD-RHO がwhileループの約 sqrt( p ) 回の反復後にnの因数pを出力すると期待する十分な理由があることがわかります。したがって、nが複合の場合、この手順では、約n 1/4の更新後にnを完全に因数分解するのに十分な約数を発見できると期待できます。おそらく最大のものを除いて、 nのpはsqrt( n )未満です。

したがって、技術的に言えば、CLRS のプレゼンテーションには終了条件がなく (おそらく、「アルゴリズム」ではなく「ヒューリスティック」および「手順」と呼ばれる理由です)、実際に何かが生成されるという保証はありません。使える。実際には、予想されるn 1/4の更新に基づいて、何らかの反復境界を設定したいと思うでしょう。

于 2011-05-18T14:47:42.643 に答える
0

これに置き換えwhile(1) { i = i + 1;てみてください：

for (i = 1; i < 2*n; ++i) {
于 2011-05-18T06:01:19.027 に答える