说白了Miller Rabin算法在信息学奥赛中的应用就一句话:

判断一个数是否是素数

费马定理：如果满足 $a^{n-1}$ ≡ 1 (mod P) 则证明n是素数。(已经给出了反例就是Carmichael数)
由于错误率极低，可以进行判断素数
如果n是一个合数，且满足 $a^{n-1}$ ≡ 1 (mod P) 则称n是一个基于a的伪素数。

但是这样的数非常少，被称为Carmichael数。比如前三个Carmichael数为561，1105，1729。。在小于1e8的数中只有255个Carmichael数。

那么对素数判断测试方法进行改进，使得测试过程中不会吧Carmichael数当作素数，就是Miller Rabin算法随机数素数测试方法
两点改进：实验了多个随机选取的基值n
当计算每个幂取模的值时，在最后的一组非平方里寻找一个以n为模的1的非凡平方根。

那么经过t轮测试,p不是素数的概率为14t

用2,3,5,7,11,13,17,19这几个数进行判断

在信息学范围内出错率为0%(不带高精) 参考： 博客园

验证了在1e7内全部正确

参考代码

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>

using namespace std;

typedef long long ll ;
const int N = 7e6 + 100 ;
ll primes[N],cnt;
bool st[N] ;

ll fast_pow(ll a,ll n,ll mod ){
    ll res = 1 ;
    while(n){
        if(n & 1) res = (res * a) % mod  ;
        a = (a * a) % mod  ;
        n >>= 1 ;
    }
    return res ;
}

bool miller_rabin(ll n){
    if(n == 1) return 0 ;
    ll t = n - 1 , u = 0 ;
    while(!(t & 1)) u ++ , t >>= 1;  //为了将n-1分解成为t * 2 ^ u ;
    for(int i = 0 ; i < 9 ; i++){
        if(n == primes[i]) return 1; 
        ll a = fast_pow(primes[i],t,n),nxt = a ;
        for(ll j = 1 ; j <= u ; j++){
            nxt = (a * a) % n ;
            if(nxt == 1 && a != 1 && a != n - 1){
                return 0 ;
            }
            a = nxt ;
        }

        if(a != 1) return 0 ;
    }
    return  1 ;
}


void init(int n){             //线性筛
    st[1] = 1 ;
    for(ll i = 2 ; i <= n ; i++){
        if(!st[i]) primes[cnt++] = i ;
        for(ll j = 0 ; primes[j] * i <= n ; j++){
            st[primes[j] * i] = 1;
            if(i % primes[j] == 0) break ;
        }
    }
}

signed main(){
    int n;
    cin >> n ;

    init(n) ;
    for(int i = 1 ; i <= n ; i ++){   //预处理一遍线性筛，然后对每个数验证miller_rabin算法正确性
        // if(!st[i]){
        //     cout << i << "是素数,miller_rabin结果为" << miller_rabin(i);
        // }
        // else {
        //     cout << i << "不是素数,miller_rabin结果为" << miller_rabin(i); 
        // }
        // if(st[i] != miller_rabin(i)) cout << " 结果正确" << endl ;
        // else  cout << "结果错误" << endl ;
        if(st[i] == miller_rabin(i)) {
            cout << i << " " << "结果错误" << endl ;
        }
    }

    cout << "验证结束" << endl ;
    return 0;
}