说这个东西之前介绍一下生日悖论：

若一年有 nn 天，屋里有约 O(n)O(\sqrt n)个人，那么他们中有两个人生日相同的概率就会达到 12\frac{1}{2}。

证明一下：
若房间中有 mm 个人，那么他们生日两两不同的概率为：

P=\prod_{i=1}^m(1-\frac{i-1}{n})$$。 由不等式 $1+x\leq e^{x}$ 得 $$P\leq\prod_{i=1}^me^{-\frac{i-1}{n}}=e^{\frac{-m(m-1)}{2n}}

故生日有相同的概率

Q≥1−e−m(m−1)2nQ\geq 1-e^{\frac{-m(m-1)}{2n}}

然后试图用Q表示m。

m(m−1)2n≤ln⁡11−Q\frac{m(m-1)}{2n}\leq \ln\frac{1}{1-Q}

m≤2nln⁡11−Qm\leq \sqrt{2n\ln\frac{1}{1-Q}}

当我们取 Q=12Q=\frac{1}{2} 时，m≈1.1774nm\approx1.1774\sqrt n。反正是于是证明了上面的定理。
关于用到的那个用来放缩的不等式，可以通过导数方法易证。

然后进入正题。
Pollard_Rho算法是快速质因数分解的一个算法。流程如下：
当要对 nn 质因数分解时，先用 Miller_Rabin判断是否是素数，如果是则返回本身。
否则，随机一个函数 f(x)f(x)（在模 nn 意义下），设置两个变量 x,yx,y，最初 x=yx=y。每次让 x=f(x),y=f(f(y))x=f(x),y=f(f(y))。一直迭代到 gcd⁡(n,abs(x−y))≠1\gcd(n,abs(x-y))\neq1。
若此时 gcd⁡\gcd 为 nn，则重新随机一个函数重复上述过程，否则找到了 nn 的一个因子，递归做上述过程。

这个算法复杂度是 O(n14log⁡n)O(n^{\frac{1}{4}}\log n) 的，已经非常快了。
下面证明一下这个算法找到 nn 的一个约数的复杂度是 O(n14)O(n^{\frac{1}{4}})。
考虑 nn 的一个最小素数 pp，我们设 x′=x%p,y′=y%px'=x\%p,y'=y\%p。当 x′=y′x'=y' 时 abs(x−y)abs(x-y) 与 nn 一定有公约数 pp。
因为每一个值 dd 都有 f(d)f(d) 做它的后继，我们可以把这些关系看作一张图，每次 x′x' 在上面走一步，y′y' 走两步。
当 x′x' 与之前某一次的 x′x' 相等时，就相当于它进环了，接下来就会一直在环上绕了。然后因为 y′y' 和 x′x' 在同一个环上绕，y′y' 每次比 x′x' 多走一步，于是最多走环长步就会相遇了。
根据上面的生日悖论，期望根号次就会进环，环长也最多是根号的，所以 x′x' 和 y′y' 期望 p\sqrt p 次就会相等。因为 p≤np\leq \sqrt n，所以一次复杂度为 n14n^\frac{1}{4}。根据上面也能看出来，最后 gcd⁡=n\gcd=n 的情况发生概率是非常小的，这等价于在模 nn 的每一个质因子的剩余系中恰好同时 x′=y′x'=y'，这样的概率实在很小。

代码脑补吧。