Pollard's Rho

这个博客讲的非常清晰

Pollard's Rho算法用于解决整数分解，期望的时间复杂度只有。给出一个整数N，返回一个N的质因数。
Pollard's Rho涉及到很多概率的问题，本质就是随机选择一个数，如果这个数，是N的质因数那么就返回这个数。否则随机选取另一个数。
首先来看一个问题，1~100内的数，随机选择一个数x=5的概率是多少？1/100，随机选择两个数x,y，的概率是多少？1/50。
生日悖论，从1~100选择k个数中，存在两个数差的绝对值=5的概率是多少？这个问题的概率是指数增长的。当k=10的时候，这个概率就达到了百分之50。
假设N的质因数是p,q直接选到p或q的概率是2/N，但是通过我们选择p,2p,3p...q,2q,3q...的概率就非常大了。因此我们使用gcd(x,n)=p当x是p或q的倍数时我们就可以将p选出来了。
1和3很容易实现，问题是2我们选择出k个数，需要保存每个数，对任意两个数计算。因此采用一种伪随机算法f(x) = (x*x+a)%N。a可以是伪随机数，但是伪随机数居然也有循环节,，f(x)若干步后一定会进入一个循环。如果我们让x与y做差，当x和y都进入循环时，整个程序就卡死了。因此需要判环。让x走一步，y走两步当x=y的时候说明进入同一个循环。这时需要更换f函数或者随机种子。
刘汝佳先生说：想象一下，假设有两个小孩子在一个“可以无限向前跑”的跑道上赛跑，同时出发。但其中一个小孩的速度是另一个的两倍。如果跑道是直的，跑得快的小孩永远在前面；但如果跑道有环，则跑得快的小孩将“追上”跑得慢的小孩。
这叫做“floyd判圈”算法。