【算法】Pollard_rho大整数分解
本帖最后由 gmh5225 于 2015-1-2 22:23 编辑用途：分解大整数，为RSA公钥私钥 作基础
Pollard_rho原理：
步骤1：
通过某种方法得到a和b（通常用b=(a*a%n+c)%n） 这里的n是要分解的大整数，a是一个随机数,范围,c是一个随机数，范围 a先备份一个给t。
步骤2：
把b=(a*a%n+c)%n 先备份一个给a ，作迭代用 , 再算d=Gcd(ABS(b-a),n)如果t==b，则返回n本身，退出循环，随机失败，或者 d不是1而且也不是n，那么此时返回的d就是一个公因子，否则循环判断步骤2。
Pollard_rho优化：
因为随机会失败，所以我们每次随机几次后，如果失败，那么 先把b给t，然后扩大随机次数继续判断，这里扩大的次数是你自己定的，一般来讲，定个2倍，这样一直循环，直到 a==b 返回n本身，或者找到公因子。
下面给出代码：
#define ll __int64
ll Pollard_rho(ll n,ll c)
{
ll a,b,t,d;
ll i=1,k=2;//这里的k就是优化过程中的随机扩大次数，i是计数器
//srand(time(0)); 这句别加了 太费时间
a=rand()%n;
t=a;//先备份一个，因为a会变化
while (true)
{
++i;//计数器+1
b=(mult_mod(a,a,n)+c)%n;
a=b;//要进行迭代，所以这样做
if (t==a) return n;//如果a==b那么返回n本身，退出循环
d=gcd(t>b?t-b:b-t,n); //gcd(abs(a-b),n)
if (d!=1&&d!=n) return d;// 这个时候d是公因子
if (i==k) //扩大随机的次数，这是一个优化
{
t=b;//把b的数值给a ,改变之前的a的数值
k+=k;//这里把随机次数扩大2倍
}
}
}以上只能返回一个公因子，如果我们想把他的全部公因子都找出来，就需要用递归
递归p和n/p (这里的p是上述函数返回的公因子) 用一个全局数组去保存这些数字
ll AllFactor int count=0//一个数组，一个下标
代码如下：
void Solve(ll n)
{
if (Miller_Rabin(n)) //如果这个公因子是素数，不可再分，则存入
{
Allfactor=n;
return;
}
ll p=n;//先把n备份一个
while (p==n) //如果失败则会返回n本身，那么继续进入此函数计算
{
p=Pollard_rho(n,rand()%(n-1)+1);
}
Solve(p);//递归这个 公因子，看他可不可以再拆分
Solve(n/p);//递归这个n/p,看看n/p可不可以拆分
}这样 Allfactor数组中存的就是拆分的因子了，例如n=16则因子是 2 2 2 2
上面的算法需要Miller_Rabin素数测试函数
膜拜搞大型算法的大大
膜拜楼主，学习了！谢谢
又是算法呀
算法好东西
谢谢楼主分享
页:
[1]