首页 > 代码库 > 关于Miller-Rabbin的一点想法
关于Miller-Rabbin的一点想法
在好久之后终于搞完了miller-rabbin素性测试，谈谈自己的理解
要判断的数设为 a，
主要思想就是运用费马小定理来搞，随机几个数x（x<=a-1），判断x^(a-1)=1(mod a)是否成立，如果有不成立,a肯定不是素数
这是有一定错误几率的，随机n个数的错误几率为4^(-n)
这么看来，肯定是多来几组随机数比较保险，10比较稳
期间加入了二次探测定理，以提高miller-rabbin的效率
二次探测定理：若p是奇素数 x^2=1 (mod p) x的解一定为 1或p-1
如果不满足此定理，一样是合数
code
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<queue> 5 #include<cmath> 6 #include<vector> 7 #include<cstdlib> 8 #include<iostream> 9 #include<ctime>10 #define ll long long 11 #define inf 214748364712 #define N 1013 using namespace std;14 15 ll quick_mul(ll a, ll b, ll n) {16 ll res = 0;17 while(b) {18 if(b&1) res = (res + a) % n;19 a = (a + a) % n;20 b >>= 1;21 }22 return res;23 }24 25 ll quick_pow(ll a, ll b, ll n) {26 ll res = 1;27 while(b) {28 if(b&1) res = quick_mul(res, a, n);29 a = quick_mul(a, a, n);30 b >>= 1;31 }32 return res;33 }34 bool miller_rabin(ll x){35 if(x==2||x==3||x==5||x==7||x==11)return 1;36 if(x==1||!(x%2)||!(x%3)||!(x%5)||!(x%7)||!(x%11))return 0;37 ll n=x-1;int k=0;38 while(!(n&1)){n>>=1;k++;}//这么做是为了顺便加上二次探测定理 39 40 srand((ll)time(0));41 for(int i=1;i<=N;i++){42 ll t=rand()%(x-1)+1,pre;43 if(!t)continue;44 t=quick_pow(t,n,x);45 pre=t;46 for(int i=1;i<=k;i++){47 t=quick_mul(t,t,x);48 if(t==1&&pre!=1&&pre!=x-1)return 0;49 pre=t;50 }51 if(t!=1)return 0;52 }53 return 1;54 55 }56 57 58 int main(){59 //freopen(".in","r",stdin);60 //freopen(".out","w",stdout);61 int l,r,cnt=0;62 scanf("%d%d",&l,&r);63 for(int i=l;i<=r;i++){64 if(miller_rabin(i))cnt++;65 }66 printf("%d",cnt);67 return 0;68 }
关于Miller-Rabbin的一点想法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。