Pollard's Rho

作者 : 开心源码 本文共683个字,预计阅读时间需要2分钟 发布时间: 2022-05-13 共261人阅读

这个博客讲的非常清晰

Pollard’s Rho算法用于处理整数分解,期望的时间复杂度只有O(N^{\frac 1 4})。给出一个整数N,返回一个N的质因数。
Pollard’s Rho涉及到很多概率的问题,本质就是随机选择一个数,假如这个数,是N的质因数那么就返回这个数。否则随机选取另一个数。
首先来看一个问题,1~100内的数,随机选择一个数x=5的概率是多少?1/100,随机选择两个数x,y,|x-y|=5的概率是多少?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判圈”算法。

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » Pollard's Rho

发表回复