Miller-Rabin与Pollard-Rho备忘

发布时间：2020-12-14 03:22:38 所属栏目：大数据来源：网络整理

导读：Miller-Rabin素性测试算法：根据费马小定理当p为素数时成立，所以如果存在一个a使x不满足此定理，则x必然不为素数。但这是充分条件而不是必要条件，所以对于每个a，可能存在满足定理的x，这时就要选取多个a同时检测，这种验证素性的方法即为Miller-Rabin算

Miller-Rabin素性测试算法：

　　根据费马小定理当p为素数时成立，所以如果存在一个a使x不满足此定理，则x必然不为素数。

　　但这是充分条件而不是必要条件，所以对于每个a，可能存在满足定理的x，这时就要选取多个a同时检测，这种验证素性的方法即为Miller-Rabin算法。

　　一般a选取前10个素数，再选取一些[1,p)的正整数即可。

Pollard-Rho质因数分解算法：

　　一种复杂度证明较为复杂的算法，主要思想是先求出n的一个因子p，然后对于p和n/p分别递归下去，如果发现p为素数则停止递归。（这里判断素数需要用到Miller-Rabin）。

　　考虑如何求出n的一个因子，现在[1,n)内随机一个整数x0，然后定义函数$f(x)equiv x^2+1 (mod n)$，先设a=x0,b=f(x0)，接下来每次a=f(a),b=f(f(b))，每次循环判断gcd(|a-b|,n)是否为n的一个因数（即不为1和n），若a=b则终止，失败。

　　这样的算法，如果将a和b直到a=b的轨迹画出来，会是一条链加一个环，a每次在上面走1步，b走两步，形如$rho$。

　　这里有一个$10^18$的大整数乘法避免快速乘的黑科技，不明白原理。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
 4 #define f(x) (mul(x,x,n)+1)%n
 5 typedef long long ll;
 6 using namespace std;
 7 
 8 ll e,n,c,d;
 9 
10 ll Rand(ll n){ return 1ll*rand()*rand()%n+1; }
11 ll gcd(ll a,ll b){ return b ? gcd(b,a%b) : a; }
12 ll mul(ll a,ll b,ll p){ ll t=a*b-(ll)((long double)a*b/p+0.5)*p; return (t<0) ? t+p : t; }
13 ll ksm(ll a,ll p){
14     ll res=1;
15     for (; b; a=mul(a,a,p),b>>=1)
16         if (b&1) res=mul(res,p);
17     return res;
18 }
19 
20 ll find(ll n,ll x){
21     ll a=x,b=f(x);
22     while (a!=b){
23         ll p=gcd(abs(a-b),n);
24         if (p>1) return (p==n) ? -1 : p;
25         a=f(a); b=f(f(b));
26     }
27     return -1;
28 }
29 
30 ll Pollard_Rho(ll n){ ll p=-1; while (p==-1) p=find(n,Rand(n-1)); return p; }
31 
32 void exgcd(ll a,ll &x,ll &y,ll p){
33     if (!b){ x=1; y=0; return; }
34     exgcd(b,a%b,y,p); y=(y-mul(a/b,p)+p)%p;
35 }
36 
37 /*
38 void fac(ll n){
39     if (miller(n)) { V.push_back(n); return; }
40     ll p=Pollard_Rho(n); fac(p); fac(n/p);
41 }*/
42 
43 int main(){
44     freopen("bzoj4522.in","r",stdin);
45     freopen("bzoj4522.out","w",stdout);
46     scanf("%lld%lld%lld",&e,&n,&c);
47     ll p=Pollard_Rho(n),r=(p-1)*(n/p-1),y;
48     exgcd(e,r,d,r); n=ksm(c,n); printf("%lld %lldn",n);
49     return 0;
50 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!