Miller-Rabin素数検出法

4118 ワード

これが複数回のランダムなアルゴリズムだと感じましたが...
アルゴリズム#アルゴリズム#
はい、ランダム大法はよくて、一般的な判断素数の中で主にこのいくつかあります:暴力列挙判断法(判断1つ:O(√n))、デュースふるい(O(nlogn)、オーラふるい(n)など、ここで1つのランダムふるい法:Miller-Rabin、これは主に2つの定理に頼って、1つはフェルマの小さい定理で、2つは2回の探知定理で、以下にアルゴリズムの流れを述べる:1つのpにとって、1.すぐにaに行きます.2.もしa^(p-1)%p!=1、これは合数で、終了3.a^(p-1)%p=1であれば、この数は素数4とは限らない.1を返すのは良い考えですが、依然としていくつかの合数が質数と判定されます.このような数は強い偽素数です.だから、二次探査の定理を使います.二次検出の定理:pが素数であり、0

#include
using namespace std;
long long x;
long long power(long long a,long long b){
long long r=1;
a=a%x;
while(b){
if(b%2) r=r*a%x;
a=a*a%x;
b/=2;
}
return r%x;
}
int main(){
cin>>x;
if(x==1){
printf("NO
");
return 0;
}
if(x==2){
printf("YES
");
return 0;
}
if(x%2==0){
printf("NO
");
return 0;
}
srand(time(NULL));
for(int i=1;i<=1000;i++){
long long y=rand(),k=x-1;
if(power(y%x,x)!=y%x){
printf("NO
");
return 0;
}
while(k==(k/2)*2){
long long l=power(y,k);
if(l==x-1){
printf("YES
");
return 0;
}
if(l<=1) k/=2;
else{
printf("NO
");
return 0;
}
}
}
printf("YES
");
return 0;
}

cは2つの数を入力して、第1の数は1つのnXnの行列を決定して、第2の数は1から値を割り当てることを決定して、値の上限(MDは半日時間を費やして、構想は死人を害しません)

連通ドメイン抽出