一、实现原理
我们以前都是怎么判断素数的呢:
试除法: 若一个正整数N为合数,则存在一个能整除N的数k,其中(2leqslant k leqslant sqrt N)。
具体实施如下:
inline int is_prime(int n){
if(n<2) return 0;
for(int i=2;i<=sqrt(n);i++){
if(n%i==0) return 0;
}
return 1;
}
这种方法的时间复杂度为(O(sqrt n))。
现在,我们希望更快地判断一个数是否为素数。
我们可以借助费马小定理来判断:
如果p是一个质数,而整数a不是p的倍数,则有
[a^{p-1}equiv 1pmod p
]
Miller-Robbin素数判定就是基于上述定理实现的,如果我们随机枚举一个(a),且(a)满足费马小定理,那么(p)就是素数。所以Miller-Robbin素数判定是一种随机性算法。
需要注意的是,我们这样判断素数的方法实际上利用的是费马小定理的逆定理。不幸的是,费马小定理的逆定理并不是一个真命题。
- 存在(a=2,p=341)时满足费马小定理,而(341=11*31)却是合数
我们把像341这样的数称作伪素数。实际上,伪素数有无穷多组。
这意味着一次判断不足以保证我们的程序正确。当然,解决这个问题也十分简单。
我们只需要重复操作大约30次,便能将正确率提升到我们期待的水平。
另外,我们使用快速幂来计算(a^{p-1})。总复杂度为(O(logn))。
下面给出Miller-Robbin素数判定的模板:
int qpow(int a,int b,int mod){//快速幂
int res=1;
while(b){
if(b&1) res=(res%mod*a)%mod;
a=(a%mod)*a%mod;
b>>=1;
}
return res;
}
bool query_prime(int x){
if(x==2)return true;
if(x==1)return false;
for(int i=1;i<=30;i++){
int base=rand()%(x-1)+1;//随机枚举a
if(qpow(base,x-1,x)!=1) return false;//计算a^(p-1)%p的值
}
return true;
}
二、应用
判断一个正整数是否为素数
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int qpow(int a,int b,int mod){//快速幂
int res=1;
while(b){
if(b&1) res=(res%mod*a)%mod;
b>>=1;
a=(a%mod)*a%mod;
}
return res;
}
inline int miller_robbin(int num){//核心代码
for(int i=1;i<=30;i++){
int base=rand()%(num-1)+1;
if(qpow(base,num-1,num)!=1) return 0;
}
return 1;
}
signed main(){
int num;
scanf("%d",&num);
if(num==1){
printf("NO");
return 0;
}
miller_robbin(num)?printf("YES
"):printf("NO
");
return 0;
}
附赠一道水题:(主要是练习素数判定)
AT1476 素数判定
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll qpow(ll a,ll b,ll mod){
ll res=1;
while(b){
if(b&1)res=(res%mod*a)%mod;
a=(a%mod)*a%mod;
b>>=1;
}
return res;
}
bool query_prime(ll x)
{
if(x==2)return true;
if(x==1)return false;
for(int i=1;i<=30;i++){
ll base=rand()%(x-1)+1;
if(qpow(base,x-1,x)!=1)return false;
}
return true;
}
int main()
{
srand(time(NULL));
ll num;
scanf("%lld",&num);
if(query_prime(num)||(num%2!=0&&num%3!=0&&num%5!=0&&num!=1))printf("Prime
");
else printf("Not Prime
");
return 0;
}
三、小结
使用Miller-Robbin素数判定,我们可以将复杂度降低至(O(logn))级别(常数阶可以被忽略)。这样比原来的方法会快很多。