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

发布于 2022-09-12  257 次阅读


我们知道一般的素数判断是\(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;
}