離散對數的波拉德ρ算法

離散對數的波拉德ρ算法是約翰·波拉德1978年所發明解決離散對數問題的算法。

算法的目標是求 $\gamma$ 使得 $\alpha ^{\gamma }=\beta$，其中 $\beta$ 屬於一個由 $\alpha$ 生成的 循環群 $G$。該算法尋找 $a$, $b$, $A$, $B$ 使得 $\alpha ^{a}\beta ^{b}=\alpha ^{A}\beta ^{B}$。若他們基於的群是一個 $n$ 階的循環群，則 $\gamma$ 是方程 $(B-b)\gamma =(a-A){\pmod {n}}$ 的其中一個解。

為求得 $a$, $b$, $A$, $B$， 該算法使用 Floyd判圈算法 在數列 $x_{i}=\alpha ^{a_{i}}\beta ^{b_{i}}$ 中尋找一個環。 假設映射 $f:x_{i}\mapsto x_{i+1}$ 是近似於隨機的，則有可能在約 ${\sqrt {\frac {\pi n}{2}}}$ 步後發現一個環。可使用一下規則來生成一個此類映射：將 $G$ 分割為三個不相交的子集 $S_{0}$，$S_{1}$ ，$S_{2}$ ，且其所含元素數量大致相等，如果 $x_{i}\in S_{0}$ 則將 $a$ 和 $b$ 加倍； 如果 $x_{i}\in S_{1}$ 則將 $a$ 自增； 如果 $x_{i}\in S_{2}$ 則將 $b$ 自增。

算法

使 G 是一個 p 階的 循環群, 且有 $\alpha ,\beta \in G$, 以及一個分割 $G=S_{0}\cup S_{1}\cup S_{2}$, 定義映射 $f: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:G\times \mathbb {Z} \to \mathbb {Z}$ 和 $h:G\times \mathbb {Z} \to \mathbb {Z}$

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

 输入 a: a 是 G 的生成元, b: G 的一个元素
 输出 整数 x 使得 ax = b, 或者失败

 初始化 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

舉例

例如一個由 2 模 $N=1019$ 生成的群（群的階是$n=1018$，2是生成元，生成群的元素模1019同餘)。這個算法可由以下 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 );
     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 算法，則整體時間複雜度近似於 ${\mathcal {O}}({\sqrt {p}})$，其中 $p$ 是 $n$ 的最大質因數。

參考文獻

• Pollard, J. M. Monte Carlo methods for index computation (mod p). Mathematics of Computation. 1978, 32 (143): 918–924. doi:10.2307/2006496. 
• Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. Chapter 3 (PDF). Handbook of Applied Cryptography. 2001 [2018-04-16]. （原始內容 (PDF)存檔於2012-02-08）.