关于 Pollard_Rho 的期望复杂度的证明

转载自 ZYQN’s Database,但是原文找不到了。

设我们要分解 $n$,$n=n_1n_2(n_1<=n_2)$,我们构造的序列为 $a_i$,$a_i~mod~n_1=b_i$

因为 $a_i$ 可近似看为随机序列,根据生日悖论可以推出其出现循环的期望步数为 $\sqrt n$,$b_i$ 同理。

因为 $n>n_1$,所以在 $b_i$ 循环之后,$a_i$ 有很大可能没有进入循环,此时 $a_i-a_j=(k_in_1+b_i)-(k_jn_1+b_j)=(k_i-k_j)n_1+(b_i-b_j)=(k_i-k_j)n_1$。于是求 gcd 即可求出 $n_1$。

因为 $b_i$ 的循环期望是 $\sqrt n_1$,而 $n_1<=\sqrt n$,所以最后是 $O(n^{\frac{1}{4}})$