miller_rabin
2025-08-27 13:26:57
发布于：广东
16阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll qpow(ll a,ll b,int mod){
ll ans=1;
while(b){
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
bool witness(ll a,ll n){//true n->合数
ll u=n-1;
int t=0;
while((u&1)==0) u>>=1,++t;
ll x1,x2;
x1=qpow(a,u,n);
for(int i=1;i<=t;++i){
x2=qpow(x1,2,n);
if(x2==1 and x1!=1 and x1!=n-1) return true;
x1=x2;
}
if(x1!=1) return true;
else return false;
}
int miller_rabin(ll n,int s){
if(n<2) return 0;
if(n==2) return 1;
if(!(n&1)) return 0;
for(int i=0;i<s and i<n;++i){
ll a=rand()%(n-1)+1;
if(witness(a,n)) return 0;
}
return 1;//n is a prime
}
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(0);
}
有帮助，赞一个