ポラード・ロー離散対数アルゴリズム

ポラード・ロー離散対数アルゴリズム (ポラード・ローりさんたいすうアルゴリズム、英語: Pollard's rho algorithm for logarithms)はジョン・ポラード英語: John Pollard1978年に導入した離散対数問題のアルゴリズムであり、ポラード・ロー素因数分解法と似た構造を持つ。

このアルゴリズムの目的は、αが生成する巡回群Gとその元βに対し、となるγを求めることにある。そのためにまず、このアルゴリズムは となるa, b, A, Bを求める。巡回群の位数nが既知の場合、γは方程式の解として求まる。

a, b, A, Bを求めるにはフロイドの循環検出法を用いて、数列のサイクルを検出する。この数列は、関数を用いて計算できるように選ぶ。fが十分にランダムなら、この数列は平均ステップでループに入る。このような関数は、例えば以下のようにすれば定義できる:まず、Gを大きさがほぼ等しい3つの集合, , の非交和に分割する。のときはabをそれぞれ2倍する。のときはaをインクリメントする。のときはbをインクリメントする。

アルゴリズム編集

Gを位数p巡回群 αGの生成元とし、 Gの分割とする。写像 を以下のように定める:

 

また、  

 

と定める。

 入力 a: Gの生成元, b: Gの元
 出力 ax = bを満たす整数xを返すか、失敗する

 Initialise a0 ← 0, b0 ← 0, x0 ← 1 ∈ G, 

 i ← 1
 loop
     xif(xi-1), 
     aig(xi-1, ai-1), 
     bih(xi-1, bi-1)

     x2if(f(x2i-2)), 
     a2ig(f(x2i-2), g(x2i-2, a2i-2)), 
     b2ih(f(x2i-2), h(x2i-2, b2i-2))

     if xi = x2i then
         rbi - b2i
         if r = 0 return failure
         xr−1(a2i - ai) mod p
         return x
     else # xix2i
         ii+1, 
         break loop
     end if
  end loop

編集

例えば、 として、2によって生成される の乗法群を考える。この群の位数は である。以下にこのアルゴリズムをC++で実装したものを示す:

#include <stdio.h>

const int n = 1018, N = n + 1;  /* N = 1019 -- 素数      */
const int alpha = 2;            /* 生成元                */
const int beta = 5;             /* 2^{10} = 1024 = 5 (N) */

void new_xab( int& x, int& a, int& b ) {
  switch( x%3 ) {
  case 0: x = x*x     % N;  a =  a*2  % n;  b =  b*2  % n;  break;
  case 1: x = x*alpha % N;  a = (a+1) % n;                  break;
  case 2: x = x*beta  % N;                  b = (b+1) % n;  break;
  }
}

int main(void) {
  int x=1, a=0, b=0;
  int X=x, A=a, B=b;
  for(int i = 1; i < n; ++i ) {
    new_xab( x, a, b );
    new_xab( X, A, B );
    printf( "%3d  %4d %3d %3d  %4d %3d %3d\n", i, x, a, b, X, A, B );
    if( x == X ) break;
  }
  return 0;
}

結果は以下の通りである (一部編集済み):

 i     x   a   b     X   A   B
------------------------------
 1     2   1   0    10   1   1
 2    10   1   1   100   2   2
 3    20   2   1  1000   3   3
 4   100   2   2   425   8   6
 5   200   3   2   436  16  14
 6  1000   3   3   284  17  15
 7   981   4   3   986  17  17
 8   425   8   6   194  17  19
..............................
48   224 680 376    86 299 412
49   101 680 377   860 300 413
50   505 680 378   101 300 415
51  1010 681 378  1010 301 416

つまり、 であるから、 であり、これを解くと という期待通りの答えが出てくる。 は素数ではないので、 という別の解もある。この場合 となってしまう。

計算量編集

実行時間はおよそ である。ポーリヒ・ヘルマンのアルゴリズム英語: Pohlig-Hellman algorithmと組み合わせた場合の実行時間は、pnの最大の素因数としたとき である。

参考文献編集