Pollard Rho算法

原理

Pollard Rho算法是一个非常玄学的算法(我个人还不是很懂其原理),作用是分解出一个数的非平凡因子(除1和它本身),通常作用于对大数的质因数分解.期望复杂度为O(n^1/4).总体来说运行效果还是相当不错的.

算法核心:y=x,x=x*x+c.其中x,y初值是随机生成的,c也是随机生成的常数,假设算法求的是n的因子,最后要判断的是g=gcd(abs(y-x),n),如果g大于1,则找到了一个因子g,否则y和x继续按公式更新,重复操作.

不过y和x都是再模n的条件下生成的,因此这么生成下去是会产生环的,因此需要判环,也就是判y是否等于x.

整个代码可以用倍增优化,需要设z用来存储每次x更新后的abs(y-x)的积,然后有大佬指出每跑完127次之后有大概率能找到一个因子.

具体细节可以参考一下以下两篇文章,这里不多叙述(不是很懂).

1 2

代码

 1 LL p_rho(LL n) 
 2 {
 3     while(1) //一定找到一个因子
 4     {
 5         LL x=rand()%n,y=x,c=rand()%n,z=1;
 6         int i=1,j=1;
 7         while(i++)
 8         {
 9             x=(q_muti(x,x,n)+c)%n; //q_muti为快速乘 
10             z=q_muti(z,abs(y-x),n);
11             if(x==y||!z) break;
12             if(!(i%127)||i==j)
13             {
14                 LL g=gcd(z,n);
15                 if(g>1) return g;
16                 if(i==j) y=x,j<<=1;
17             }
18         }
19     }
20 }

这里再给出完整的质因数分解模板,需要同时用到Miller-Rabin素数测试和Pollard Rho算法

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 typedef unsigned long long ULL;
  5 typedef long long LL;
  6 typedef long double LB;
  7 const int INF_INT=0x3f3f3f3f;
  8 const LL INF_LL=0x3f3f3f3f3f3f3f3f;
  9 
 10 map<LL,int> prime_factor; //分别表示质因子和幂
 11 
 12 LL Abs(LL x)
 13 {
 14     if(x<0) return x*-1;
 15     return x;
 16 }
 17 
 18 LL gcd(LL a,LL b)
 19 {
 20     return b?gcd(b,a%b):a;
 21 }
 22 
 23 LL q_muti(LL a,LL b,LL p) //防爆快速乘
 24 {
 25     LL res=0;
 26     a%=p;
 27     while(b)
 28     {
 29         if(b&1) res=(res+a)%p;
 30         a=(a<<1)%p;
 31         b>>=1;
 32     }
 33     return res;
 34 }
 35 
 36 LL q_power(LL a,LL b,LL p) //快速幂
 37 {
 38     LL res=1;
 39     a%=p;
 40     while(b)
 41     {
 42         if(b&1) res=q_muti(res,a,p);
 43         a=q_muti(a,a,p);
 44         b>>=1;
 45     }
 46     return res;
 47 }
 48 
 49 bool m_l(LL x,LL a) //Miller-Rabin
 50 {
 51     if(q_power(a,x-1,x)!=1) return false;
 52     LL q=x-1;
 53     while(!(q&1))
 54     {
 55         q>>=1;
 56         LL t=q_power(a,q,x);
 57         if(t==1) continue;
 58         if(t==x-1) break;
 59         return false;
 60     }
 61     return true;
 62 }
 63 
 64 bool is_prime(LL x) //判素数
 65 {
 66     if(x==0||x==1) return false;
 67     if(x==2||x==3) return true;
 68     else
 69     {
 70         int k=10;
 71         for(int i=0;i<k;i++)
 72         {
 73             LL a=rand()%(x-3)+2;
 74             if(!m_l(x,a)) return false;
 75         }
 76         return true;
 77     }
 78 }
 79 
 80 LL p_rho(LL n)
 81 {
 82     while(1) //一定找到一个因子
 83     {
 84         LL x=rand()%n,y=x,c=rand()%n,z=1;
 85         int i=0,j=1;
 86         while(++i)
 87         {
 88             x=(q_muti(x,x,n)+c)%n;
 89             z=q_muti(z,Abs(y-x),n);
 90             if(x==y||!z) break;
 91             if(!(i%127)||i==j)
 92             {
 93                 LL g=gcd(z,n);
 94                 if(g>1) return g;
 95                 if(i==j) y=x,j<<=1;
 96             }
 97         }
 98     }
 99 }
100 
101 LL find_prime(LL n) //找质因子
102 {
103     if(is_prime(n)) return n;
104     return find_prime(p_rho(n));
105 }
106 
107 void factorize(LL n)//分解
108 {
109     while(n!=1)
110     {
111         LL p=find_prime(n);
112         while(!(n%p)) prime_factor[p]++,n/=p;
113     }
114 }
115 
116 void solve(LL n)
117 {
118     if(n<=1)
119     {
120         printf("None\n");
121         return ;
122     }
123     prime_factor.clear();
124     factorize(n);
125     for(map<LL,int>::iterator i=prime_factor.begin();i!=prime_factor.end();i++)
126         printf("prime factor:%lld power:%d\n",i->first,i->second);
127 }
128 
129 int main()
130 {
131 //    freopen("std.in","r",stdin);
132 //    freopen("std.out","w",stdout);
133     srand(time(0)); //随机数生成
134     LL n;
135     while(~scanf("%lld",&n)) solve(n);
136     return 0;
137 }