[MillerRabin模板]大数的素数判断 - 米勒罗宾素性检验

我们知道一般的素数判断是\(O(\sqrt{n})\)的复杂度的，当\(n \le 10^{14}\)且仅判断个数较少的情况下尚且能用，如果需要判断k个较大的数字（\(n \le 10^{18}\)）的数字，估计一下要运算\(k * 10^8\)之多，显然无法接受。

介绍 / Introduction

这里介绍的MillerRabin算法是一种可以在\(O(k*log^{2}{2})\)的复杂度内进行对n的素性检验的方法，k是检验数的个数，一般在10以内，复杂度骤降。

作为竞赛使用不必深究其原理，感兴趣的可以看看这些文章：

Miller Rabin算法详解 - 自为风月马前卒 - 博客园 (cnblogs.com)

【朝夕的ACM笔记】数论-Miller Rabin素数判定 - 知乎 (zhihu.com)

基本原理就是费马检验 + 二次探测理论，当然这是一个随机算法，只是它在足够大的范围内准确度极高（接近100%）。

经过k次检测，判断素性的失败率小于\(\frac{1}{4^k}\)，已经基本上可以认为是正确的了，至少在OI范围内不会出错。

例题：U148828 素数判断(Miller-Rabin模板) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

模板 / Templete

#define int long long // 为了方便下面的longlong都用int表示

int qmi(int a, int b, int p) // 快速幂
{
    int res = 1;
    while (b)
    {
		// 注意！中间结果可能溢出，需要使用__int128过渡
        if (b & 1)res = (__int128)res * a % p; 
        a = (__int128)a * a % p, b >>= 1;
    }
    return res;
}

bool isprime(int x)//Miller_Rabin
{
	//特判 
    if (x < 3)return x == 2;
    if (x % 2 == 0)return false;
    //用下面这几个数字判断不会出错 
    int A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}, d = x - 1, r = 0;
    while (d % 2 == 0)d >>= 1, ++r;
    for (auto a : A)
    {
        int v = qmi(a, d, x);
        if (v <= 1 || v == x - 1)continue;
        for (int i = 0; i < r; ++i)
        {
            v = (__int128)v * v % x;
            if (v == x - 1 && i != r - 1)
            {
                v = 1;
                break;
            }
           if (v == 1)return false;
        }
        if (v != 1)return false;
    }
    return true;
}