ポラード・ロー素因数分解法(Pollard's rho algorithm) PKU 2447とか．

PKU Algorithm

以下は嘘吐いてる可能性が結構あるので気をつけて！！

ρ法は篩などでは見つけられない大きさの素因数を見つけるアルゴリズム．

理論的なことは完全に理解していないので僕が説明するよりwikipedia:ポラード・ロー素因数分解法とかhttp://matsumoto-lab.hp.infoseek.co.jp/chapter02/algo02.htmlとかhttp://idm.s9.xrea.com/factorization/rho.htmlをよんだほうがいいです(´・ω・`)むずい．

ρ法のオーダーは，見つける素因数をpとするとsqrt(p)で50%程度らしい．

また実装の注意点として

  • long longの掛け算はオーバーフローする．
    • 掛け算を足し算で実装する．
  • 確率的なものなので，見つからないこともある．
    • Miller-Rabin Testなどで素数でないことを確認した上でρ法を行う．
    • f(x) = x^2 + cのcの値を変えて繰り返し試行．
  • 帰ってきた結果は素数とは限らない．
    • 予め試し割り(篩など)で小さな素数を取り除いておくとよい．

実装は次の通り

typdef long long Int;
// a * b % mを返す．
Int multMod(Int a,Int b,Int m){
  Int res = 0;
  a %= m;
  while (b){
    if (b & 1){
      res = (res + a) % m;
    }
    a = (a * 2) % m;
    b = b / 2;
  }
  return res;
}

// cははじめ1を入れる．
// numが素数の場合無限ループしてしまう．判定もするなら適度なcで打ち切る．*/
Int PollardRho(Int num,Int c){
  Int x,y,p;
  x = y = p = 1LL;
  while (p == 1){
    x = (multMod(x,x,num) + c) % num;
    Int ty = (multMod(y,y,num) + c) % num;
    y = (multMod(ty,ty,num) + c) % num;
    if (x == y) return PollardRho(num,c+1);
    p = gcd(num,llabs(x-y));
  }
  return p;
}

1811 Prime Testや2447 RSAで確認．実際にはcの値が1の時点で答えは見つかっているようだ．1811では2^16以下の数で篩を作りためし割りした．

また，Brentの改良を入れると次のようになる．

// Brentの改良
Int PollardRho(Int num,Int c){
  Int x,y,p;
  x = p = 1LL;
  int next = 2,i=1;
  while (p == 1){
    ++i;
    if (i == next){
      y = x;
      next *= 2;
    }
    x = (multMod(x,x,num) + c) % num;
    if (y == x) return PollardRho(num,c+1);
    p = gcd(num,llabs(x-y));
  }
  return p;
}

2447では速度上がらなかった．しょんぼり．

今回間違い多そうなので指摘してくだしあ．