首页 > 代码库 > Miller-Rabin 素性测试
Miller-Rabin 素性测试
根据费马小定理，若p为素数，则必有a^(p-1) mod p=1 对和p互质的a成立。
根据二次探测定理：如果p是素数，且0<x<p，则方程x^2 mod p=1的解为1或p-1。
所以若p为素数，则必有a^(p-1) mod p 的平方根为1或-1
分解p-1为d*2^s，其中d为奇数
从i=0逐次计算a^(d*2^(s-i))，相当于“开方”，若得到-1或追查到a^d=1 (mod p)，则p通过测试，否则不通过
时间复杂度O(k*(logn)^3) （其中k为选的a的个数（the more the better?））
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 using namespace std; 5 6 const int prime[9]={2,3,5,7,11,13,17,19,23}; 7 8 int n; 9 10 int quick(int a,int b,int mod){11 int sum=1;12 for(;b;b>>=1,a=a*a%mod)13 if(b&1) sum=sum*a%mod;14 return sum;15 }16 17 bool Rabin_Miller(int p,int a){18 if(p==2) return 1;19 if((p&1)==0||p==1) return 0;20 int d=p-1;21 while((d&1)==0) d>>=1;22 int m=quick(a,d,p);23 if(m==1) return 1;24 for(;d<p;d<<=1,m=m*m%p)25 if(m==p-1) return 1;26 return 0;27 }28 29 bool isprime(int x){30 for(int i=0;i<9;i++){31 if(x==prime[i]) return 1;32 if(!Rabin_Miller(x,prime[i])) return 0;33 }34 return 1;35 }36 37 int main(){38 scanf("%d",&n);39 if(isprime(n)) puts("Yes!");40 else puts("No!");41 return 0;42 }
Miller-Rabin 素性测试
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。