数学--数论--Miller_Rabin判断一个大数是不是素数（随机算法）

前提知识
1，费马定理：ap−1=1(mod p)a^{p-1}=1(mod\ p)ap−1=1(mod p)点我
2，二次探测定理：x2≡1(mod p)⇒x=1∣∣p−1x^{2}\equiv 1(mod\ p)\Rightarrow x=1||p-1x2≡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;

}

巴特西

数学--数论--Miller_Rabin判断一个大数是不是素数（随机算法）

最新文章

热门文章