# 离散对数 Pollard Rho 算法

## 算法

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

{\displaystyle {\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


## 举例

 #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