ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

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

2022年9月12日 154点热度 0人点赞 0条评论

我们知道一般的素数判断是\(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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: miller-rabin 二次探测理论 模板 竞赛 米勒罗宾 素性检验 素数 费马
最后更新:2022年9月12日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 介绍 / Introduction
  • 模板 / Templete

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号