⼤数因数分解Pollard_rho算法详解
有⼀类问题，要求我们将⼀个正整数x，分解为两个⾮平凡因⼦（平凡因⼦为1与x）的乘积x=ab。
显然我们需要先检测x是否为素数（如果是素数将⽆解），可以使⽤来进⾏测试。
⼤数分解最简单的思想也是试除法，就是从2到sqrt(n)，⼀个⼀个的试验，直到除到1或者循环完，最后判断⼀下是否已经除到1了即可。（当然这是幼稚做法，复杂度是相当⾼的，不然我就是想打试除法多⽅便呀）
Pollard Rho原理
⽣⽇悖论
如果⼀年只有365天（不计算闰年），且每个⼈的⽣⽇是任意⼀天的概率均相等，那么只要随机选取23⼈，就有50%以上的概率有两⼈同⼀天⽣⽇
解释：第⼀个⼈不会和前⾯的⼈重⽣⽇（因为前⾯没有⼈），第⼆个⼈不重⽣⽇的概率为364/365，第三个⼈363/365……以此类推，那么只要到第23个⼈，就有
，说明这时就有50%以上的概率有两⼈同⽣⽇
更多的，当⼀年有n天时，只要⼈数到达Θ(sqrt(n))的数量级，有⾄少两个⼈同⼀天⽣⽇的概率就可以达到50%以上
图象表达：
利⽤⽣⽇悖论
利⽤⽣⽇悖论来因数分解，重要的思想就是随机。
已知我们随机地从[2,N-1]中选择出⼀个数是N的因数的概率是极⼩的，这也就意味着需要重复随机选择来提⾼正确率。
那么如果我们不是只选择⼀个数，⽽是选择k个数，保证其中两个数的差值是N的因数。
⽽如果其中两个数x，y的差值为N的因数，就⼀定会有gcd(|x-y|,N)>1
假设N只有两个因数(除去⾃⼰和1)p和q的情况下，那么就意味着此时只有这两个数能整除N
但是如果我们要求的是有多少个数x保证gcd(x,N)>1，此时答案就很多了，有p+q-2个
博客为什么没人用了
于是我们就得出了⼀个简单的策略：
1.在区间[2,N-1]中随机选取k个数，x1~k
2.判断是否存在gcd(xi-xj,N)>1，若存在，则显然gcd(xi-xj,N)是N的⼀个因数
同时也出现了⼀个问题，就是我们需要选取⼤约（N¼）个数，内存显然是不可能够的，那么⼜要如何解决这个问题呢？于是Pollard-rho算法就出现了。
Pollard Rho算法
因为数字太多内存不够，所以Pollard-rho只把连续的两个数存在内存中。
也就是说，我们并不会选出k个数，⽽是⼀个⼀个地⽣成伪随机数，并检查连续的两个数是否符合条件。
我们会⽤⼀个函数来⽣成伪随机数，就是这个→f(x)=(x2+a)%N
其中的a可以⾃⼰指定或rand()⽣成，但是这样也伴随了⼀个问题就是这个函数⽣成的伪随机数还是有规律的，会⽆限循环。
于是就会出现像希腊字母ρ⼀样的情况，这也是为什么这个算法名字中含有rho
那么我们⼜要如何避免这种情况呢？
⾸先为了保证没有答案可能被遗漏，那么⾄少要把这个环完整的扫⼀遍。
联想⼀下⼀个⽐较常见的问题，就是⼩学数学题做过的两个⼈在环形操场上跑步，在同时起跑的情况下，当速度快的那个⼈追上速度慢的那个⼈的时候，⼀定已经多跑了⼀圈，也就是说此时两⼈肯定都⾄少跑完了⼀圈，恰好符合我们的要求。
那么就是说我们要⽤两个变量来存储，⼀个⽤v的速度扫描环，⼀个⽤2v的速度，如果当两个变量相等时还没有到答案，就退出这个环，重新取随机数，再次带⼊上⾯提到的函数中。
这⾥有⼀点要说明⼀下，就是为什么快的速度⼀定要是慢的速度的两倍⽽不能更⼤。
假设快的速度为kv(k>2)，整个环的路程为s，快的追上慢的所需时间为t，那么我们可以列出式⼦：
kvt−vt = s ⇒ (k−1)vt = s ⇒ vt = sk−1
因为 k > 2，所以 k-1 > 1，那么就有 s/(k−1) < s
，也就意味着此时⽤来判断答案是否符合条件的(也就是速度较慢的那个)还没有扫描完整个环，那么就有可能会有答案被遗漏。
以上就是完整的Pollard-rho算法过程，接下来上代码
void Pollard_rho(long long N){
long long a=rand()%N+1;//随机⽣成常数a
long long x1,x2,d;
x1=x2=rand()%N+1;
while(1){
x1=count(x1,cc);x2=count(count(x2,cc),cc);
if(x1==x2) {x1=x2=rand()%N+1;cc=rand()%N+1;}
d=gcd(abs(x2-x1),N);
if(d>1&&d<N){p=d;q=N/p;return;}//p,q记录N的因数
}
return;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。