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

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

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

a, b, A, Bを求めるにはフロイドの循環検出法を用いて、数列$x_{i}=\alpha ^{a_{i}}\beta ^{b_{i}}$のサイクルを検出する。この数列は、関数$f\colon x_{i}\mapsto x_{i+1}$を用いて計算できるように選ぶ。fが十分にランダムなら、この数列は平均${\sqrt {\frac {\pi n}{2}}}$ステップでループに入る。このような関数は、例えば以下のようにすれば定義できる：まず、Gを大きさがほぼ等しい3つの集合$S_{0}$, $S_{1}$, $S_{2}$の非交和に分割する。$x_{i}\in S_{1}$のときはaとbをそれぞれ2倍する。$x_{i}\in S_{2}$のときはaをインクリメントする。$x_{i}\in S_{0}$のときはbをインクリメントする。

アルゴリズム

Gを位数pの巡回群、$\alpha ,\beta \in G$でαはGの生成元とし、$G=S_{0}\cup S_{1}\cup S_{2}$をGの分割とする。写像$f\colon G\to G$を以下のように定める：

$f(x)={\begin{cases}\beta x&x\in S_{0}\\x^{2}&x\in S_{1}\\\alpha x&x\in S_{2}\end{cases}}$

また、$g\colon G\times \mathbb {Z} \to \mathbb {Z}$と$h\colon G\times \mathbb {Z} \to \mathbb {Z}$を

${\begin{aligned}g(x,n)&={\begin{cases}n&x\in S_{0}\\2n\ ({\bmod {\ }}p)&x\in S_{1}\\n+1\ ({\bmod {\ }}p)&x\in S_{2}\end{cases}}\\h(x,n)&={\begin{cases}n+1\ ({\bmod {\ }}p)&x\in S_{0}\\2n\ ({\bmod {\ }}p)&x\in S_{1}\\n&x\in S_{2}\end{cases}}\end{aligned}}$

と定める。

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

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

 i ← 1
 loop
     xi ← f(xi-1), 
     ai ← g(xi-1, ai-1), 
     bi ← h(xi-1, bi-1)

     x2i ← f(f(x2i-2)), 
     a2i ← g(f(x2i-2), g(x2i-2, a2i-2)), 
     b2i ← h(f(x2i-2), h(x2i-2, b2i-2))

     if xi = x2i then
         r ← bi - b2i
         if r = 0 return failure
         x ← r−1(a2i - ai) mod p
         return x
     else # xi ≠ x2i
         i ← i+1, 
         break loop
     end if
  end loop

例

例えば、$N=1019$として、2によって生成される$\mathbb {Z} /N\mathbb {Z}$の乗法群を考える。この群の位数は$n=1018$である。以下にこのアルゴリズムを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

つまり、$2^{681}5^{378}=1010=2^{301}5^{416}{\pmod {1019}}$であるから、$(416-378)\gamma =681-301{\pmod {1018}}$であり、これを解くと$\gamma _{1}=10$という期待通りの答えが出てくる。$n=1018$は素数ではないので、$\gamma _{2}=519$という別の解もある。この場合$2^{519}=1014=-5{\pmod {1019}}$となってしまう。

計算量

実行時間はおよそ${\mathcal {O}}({\sqrt {n}})$である。ポーリヒ・ヘルマンのアルゴリズム（英語: Pohlig-Hellman algorithm）と組み合わせた場合の実行時間は、pをnの最大の素因数としたとき${\mathcal {O}}({\sqrt {p}})$である。

参考文献

• Pollard, J. M. (1978). “Monte Carlo methods for index computation (mod p)”. Mathematics of Computation 32 (143): 918–924. doi:10.2307/2006496. 
• Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (2001). “Chapter 3”. Handbook of Applied Cryptography. http://www.cacr.math.uwaterloo.ca/hac/about/chap3.pdf