数学--数论--Miller_Rabin判断一个大数是不是素数（随机算法）
数学--数论--Miller_Rabin判断一个大数是不是素数（随机算法）
前提知识 1，费马定理： a p − 1 = 1 ( m o d p ) a^{p-1}=1(mod\ p) ap−1=1(mod p)?点我 2，二次探测定理： x 2 ≡ 1 ( m o d p ) ⇒ x = 1 ∣ ∣ p − 1 x^{2}\equiv 1(mod\ p)\Rightarrow x=1||p-1 x2≡1(mod p)⇒x=1∣∣p−1?点我 但我们注意到，费马定理其逆定理不能直接用来判断素数，必须要枚举很多数，一般情况下我们可以枚举到1000左右，就可以把long long范围内的大部分数给判断完成。
也有例外，即存在一种极端反例卡迈克尔数（一种合数），对于任何卡迈克尔叔，费马定理都成立。虽然这种极少，在1e8范围内的整数中，只有255个卡迈克尔数。但不管怎么说还是会被出题人卡死，或者被人hack，虽然这种算法的出错率为4^-k（k为测试数据的个数）。
而为了防止这种情况出现，有一种东西，叫二次探测定理： 如果p是奇素数，则 x≡1(mod p)的解为x=1或x=p-1(mod p)，这个由模运算的性质易得。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int times = 10;
ll fast_mod(ll a,ll b,ll mod)//计算2^q的过程
{
ll res = 0;
while(b){
if(b & 1) res = res + a;
a <<= 1;
if(a >= mod) a -= mod;
if(res >= mod) res -= mod;
b >>= 1;
}
return res;
}
ll fast_pow_mod(ll a,ll b,ll mod)//快速幂算出a^m
{
ll res = 1;
while(b){
if(b & 1) res = (res * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return res;
}
bool check(ll a,ll m,ll p,ll n)//对于每次随机的a进行测试
{
ll temp = fast_pow_mod(a,m,n),ret = temp;
for(int i = 0;i < p;++i){
ret = fast_mod(temp,temp,n);
if(ret == 1 && temp != n - 1 && temp != 1) return true;
temp = ret;
}
return ret != 1;
}
bool Miller_Pabin(ll n)//Miller测试的主体结构
{
if(n < 2) return false;
if(n == 2) return true;
if(n & 1 == 0) return false;//对于偶数的优化
ll p = 0,x = n - 1;//p为Miller测试的q，x为Miller测试的m
while(x & 1 == 0){
x >>= 1;
p++;
}
srand(time(NULL));
for(int i = 0;i < times;++i){
ll o = rand() % (n - 1) + 1;//o就是Miller测试的底数a
if(check(o,x,p,n)) return false;
}
return true;
}
int main()
{
ios::sync_with_stdio(false);
int t;
cin >> t;
while(t--){
long long n;
cin >> n;
cout << (Miller_Pabin(n) ? "Prime" : "Not a Prime") << endl;
}
return 0;
}腾讯云开发者
