【算法】Pollard_rho大整数分解

用途：分解大整数，为RSA公钥私钥 作基础


Pollard_rho原理：
步骤1：
通过某种方法得到a和b（通常用b=(a*a%n+c)%n） 这里的n是要分解的大整数，a是一个随机数,范围[0,n-1],c是一个随机数，范围[1,n-1]   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本身，或者找到公因子。

下面给出代码：

1. #define ll __int64
   
2. ll Pollard_rho(ll n,ll c)
   
3. {
   
4.         ll a,b,t,d;
   
5.         ll i=1,k=2;//这里的k就是优化过程中的随机  扩大次数，i是计数器
   
6.         //srand(time(0)); 这句别加了 太费时间
   
7.         a=rand()%n;
   
8.         t=a;//先备份一个，因为a会变化
   
9.         while (true)
   
10.         {
    
11.                 ++i;//计数器+1
    
12.                 b=(mult_mod(a,a,n)+c)%n;
    
13.                 a=b;//要进行迭代，所以这样做
    
14.                 if (t==a) return n;//如果a==b  那么返回n本身，退出循环
    
15.                 d=gcd(t>b?t-b:b-t,n); //gcd(abs(a-b),n)
    
16.                 if (d!=1&&d!=n) return d;// 这个时候d是公因子
    
17.                 if (i==k)   //扩大随机的次数，这是一个优化
    
18.                 {
    
19.                         t=b;//把b的数值给a ,改变之前的a的数值
    
20.                         k+=k;//这里把随机次数扩大2倍
    
21.                 }
    
22.         }
    
23. }

复制代码

以上只能返回一个公因子，如果我们想把他的全部公因子都找出来，就需要用递归
递归p和n/p (这里的p是上述函数返回的公因子)   用一个全局数组去保存这些数字
ll AllFactor[100] int count=0//一个数组，一个下标

代码如下：

1. void Solve(ll n)
   
2. {
   
3.         if (Miller_Rabin(n)) //如果这个公因子是素数，不可再分，则存入
   
4.         {
   
5.                 Allfactor[count++]=n;
   
6.                 return;
   
7.         }
   
8.         ll p=n;//先把n备份一个
   
9.         while (p==n) //如果失败则会返回n本身，那么继续进入此函数计算
   
10.         {
    
11.                 p=Pollard_rho(n,rand()%(n-1)+1);
    
12.         }
    
13.         Solve(p);//递归这个 公因子，看他可不可以再拆分
    
14.         Solve(n/p);//递归这个n/p,看看n/p可不可以拆分
    
15. }

复制代码

这样 Allfactor数组中存的就是拆分的因子了，例如n=16  则因子是 2 2 2 2
上面的算法需要Miller_Rabin素数测试函数

膜拜搞大型算法的大大

膜拜楼主，学习了！谢谢

又是算法呀

算法好东西

谢谢楼主分享