miller——rabin判断素数
我们首先看这样一个很简单的问题:判定正整数(n)是否为素数 最简单的做法就是枚举(2)到(n)的所有数,看是否有数是(n)的因数,时间复杂度(O(n)) 稍微优化一下发现只要枚举(2)到(sqrt{n})中的数就可以了 然后发现数据范围(nleq 10^{18}),时间复杂度直接就死掉了QAQ 我们就要考虑新的方法了 首先引入两个定理 1、费马小定理 如果(p)是素数,且(gcd(a,b)=1),那么(a^{p-1}equiv 1(mod n)) 证明什么的你随便找本数论书自己翻一下 注意它的逆定理不一定成立(或者说是它的逆定理在大多数情况下都成立) 2、二次探测定理(其实这也没有一个准确的名字) 如果(p)是奇素数,(x<p),且(x^2equiv1(mod p)),那么(x=1)或(xp=-1) 证明:由同余式知(x^2-1equiv0(mod p)),即(p|(x+1)(x-1)) ? 又由(p)是素数知(p|x-1)或(p|x+1),解得(x=1)或(x=p-1) 诶等等zzr没事给证明干嘛?zzr不是最讨厌证明了吗 由上面很简单的证明过程我们可以发现,(x=1)和(x=p-1)这两个解其实是对所有的(p)都成立的 即无论(p)取什么值(x)取上面两个值是一定可以的 但是当(p)是一个合数的时候,此时原同余方程的解(x)就不只上面这两个了,而是会有多个 换一句话说:如果上面的(x)取到了1和(p-1)以外的数,就说明(p)不是一个素数了 我们主要利用上面两个性质来进行素数判定 1、取(2^q*m=n-1)((q,m)均为正整数且(m)为奇数),同时任意取小于(n)的正整数(a) 2、求出(a^{n-1}text%n),如果这个值不为1那么(n)一定是合数(利用费马小定理) 3、遍历(i),使得(1leq i leq q),如果(2^i*mtext%n=1)并且(a^{i-1}*mtext%n!=1或n-1),那么由二次探测定理就知道原同余方程出现一个特殊解,说明(n)不是一个素数 上面的方法有一个小问题:由于费马小定理的逆定理不一定成立(在大多数情况下成立),因此有时我们会对(n)进行误判,具体的,每做一次发生误判的概率是(frac{1}{4}) 解决的方法在上面的解法中也有体现:换用不同的(a),多进行几次即可 好了上面就是完整的miller-rabin测试了 一道例题:poj3518Prime Gap 题意:两个相邻的素数的差值叫做Prime Gap。输入一个K,求K两端的素数之差,如果K本身是一个素数,输出0; 分析:其实数据很小你直接筛一下也可以 ? 或者你直接暴力寻找当前这个数相邻的数是否是质数,两端分别记录第一次找到的质数即可 #include<iostream> #include<string.h> #include<string> #include<stdio.h> #include<stdlib.h> #include<algorithm> #include<vector> #include<queue> #include<map> using namespace std; #define int long long int n; int read() { int x=0,f=1;char ch=getchar(); while ((ch<‘0‘) || (ch>‘9‘)) {if (ch==‘-‘) f=-1;ch=getchar();} while ((ch>=‘0‘) && (ch<=‘9‘)) {x=x*10+(ch-‘0‘);ch=getchar();} return x*f; } int mul(int x,int y,int n) { x%=n;y%=n; int ans=0,sum=x; while (y) { int tmp=y%2;y/=2; if (tmp) ans=(ans+sum)%n; sum=(sum+sum)%n; } return ans; } int qpow(int x,int n) { int ans=1,sum=x; while (y) { int tmp=y%2;y/=2; if (tmp) ans=mul(ans,sum,n); sum=mul(sum,n); } return ans; } bool prime(int m,int q,int a,int n) { int now=qpow(a,m,n); if ((now==1) || (now==n-1)) return 1; int i; for (i=1;i<=q;i++) { int x=mul(now,now,n); if ((x==1) && (now!=1) && (now!=n-1)) return 0; now=x; } if (now!=1) return 0;//其实这里是将费马小定理的检测放在了最后,省去再做一次快速幂 return 1; } bool miller_rabin(int x) { if (x==2) return 1; if ((x<2) || (x%2==0)) return 0; int num=x-1,tim=0; while ((num) && (num%2==0)) {num/=2;tim++;} //cout << num << " " <<tim << endl; int i; for (i=1;i<=10;i++)//一般都会进行20次左右,不过数据范围小对吧2333 { int a=rand()%(x-1)+1; if (!prime(num,tim,a,x)) return 0; } return 1; } void work() { if (miller_rabin(n)) {printf("0n");return;} //cout <<1; int l=n-1,r=n+1; while (!miller_rabin(l)) l--; while (!miller_rabin(r)) r++; printf("%dn",r-l); } signed main() { n=read(); while (n) { work(); n=read(); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |