首页 > 代码库 > Miller_Rabin素数测试
Miller_Rabin素数测试
1 #include<iostream> 2 #include<cmath> 3 #include<cstdio> 4 #include<cstring> 5 #include<algorithm> 6 using namespace std; 7 8 long long mul(long long a,long long n,long long mo){ 9 long long ans=0;10 while (n){11 if (n&1) ans=(ans+a)%mo;12 a=(a+a)%mo;13 n/=2;14 }15 return ans;16 }17 18 long long pow(long long a,long long n,long long mo){19 long long ans=1;20 while (n){21 if (n&1) ans=mul(ans,a,mo);22 a=mul(a,a,mo);23 n/=2;24 }25 return ans;26 }27 28 bool Miller_Rabin(long long n){29 if (n<=2){30 if (n==2) return true;31 else return false;32 }33 if (n%2==0) return false;34 long long u=n-1;35 while (u%2==0){36 u/=2;37 }38 int t=1e2;39 while (t--){40 long long a=(rand()%(n-2))+2;41 long long x=pow(a,u,n);42 long long w=u*2;43 long long y=mul(x,x,n);44 while (w<n){45 if (y==1&&x!=1&&x!=(n-1)) return false;46 x=y;47 y=mul(y,y,n);48 w*=2;49 }50 if (x!=1) return false;51 }52 return true;53 }54 55 int main(){56 int t;57 scanf("%d",&t);58 while (t--){59 long long n;60 scanf("%lld",&n);61 if (Miller_Rabin(n)) printf("Yes\n");62 else printf("No\n");63 }64 65 }
费马小定理：对于质数p和任意整数a，有a^p ≡ a(mod p)(同余)。反之，若满足a^p ≡ a(mod p)，p也有很大概率为质数。将两边同时约去一个a，则有a^(p-1) ≡ 1(mod p)
也即是说：假设我们要测试n是否为质数。我们可以随机选取一个数a，然后计算a^(n-1) mod n，如果结果不为1，我们可以100%断定n不是质数。
否则我们再随机选取一个新的数a进行测试。如此反复多次，如果每次结果都是1，我们就假定n是质数。
该测试被称为Fermat测试。需要注意的是：Fermat测试不一定是准确的，有可能出现把合数误判为质数的情况。
Miller和Rabin在Fermat测试上，建立了Miller-Rabin质数测试算法。
与Fermat测试相比，增加了一个二次探测定理：
如果p是奇素数，则 x^2 ≡ 1(mod p)的解为 x ≡ 1 或 x ≡ p - 1(mod p)
如果a^(n-1) ≡ 1 (mod n)成立，Miller-Rabin算法不是立即找另一个a进行测试，而是看n-1是不是偶数。如果n-1是偶数，另u=(n-1)/2，并检查是否满足二次探测定理即a^u ≡ 1 或 a^u ≡ n - 1(mod n)。
举个Matrix67 Blog上的例子，假设n=341，我们选取的a=2。则第一次测试时，2^340 mod 341=1。由于340是偶数，因此我们检查2^170，得到2^170 mod 341=1，满足二次探测定理。同时由于170还是偶数，因此我们进一步检查2^85 mod 341=32。此时不满足二次探测定理，因此可以判定341不为质数。
Miller_Rabin素数测试
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。