Miller Rabin算法：大质数判断

问题概述：判断一个数n是不是质数(n<=10^18)

输入样例：                              对应输出：

7                                              Yes

费马小定理：如果p是质数，且a,p互质，那么a^(p-1)%p==1

Miller-Rabin算法的理论基础：如果p是一个大于2的质数，先将p-1表示成2^s*r的形式(r是奇数)，令a是和n互素的任

意整数，那么a^r%p==1或对某个j(0<=j<=s-1,j∈Z)，等式a^(2^j*r)%p==±1成立

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
using namespace std;
#define LL long long
LL Multi(LL a, LL b, LL mod)
{
LL ans = 0;
a %= mod;
while(b)
{
if(b%2==1)  ans = (ans+a)%mod, b--;
else  a = (a+a)%mod, b /= 2;
}
return ans;
}

LL Pow(LL a, LL b, LL mod)
{
LL ans = 1;
a %= mod;
while(b)
{
if(b&1)  ans = Multi(ans, a, mod), b--;
else  a = Multi(a, a, mod), b /= 2;
}
return ans;
}

int Miller_Rabin(LL n)
{
int i, j, k;
LL a, x, y, mod;
if(n==2)  return 1;
if(n<2 || n%2==0)  return 0;
k = 0, mod = n-1;
while(mod%2==0)
{
k++;
mod /= 2;
}
for(i=1;i<=10;i++)
{
a = rand()%(n-1)+1;//随机生成一个小于n的正整数
x = Pow(a, mod, n);
y = 0;
for(j=1;j<=k;j++)
{
y = Multi(x, x, n);
if(y==1 && x!=1 && x!=n-1)
return 0;
x = y;
}
if(y!=1)
return 0;
}
return 1;
}

int main(void)
{
LL n;
scanf("%I64d",&n);
if(Miller_Rabin(n))
printf("Yes\n");
else
printf("No\n");
return 0;
}