1011 字
5 分钟
Miller-Rabin 素数判定算法整理
Miller-Rabin 素数判定算法是可以快速判定质数的一个概率性算法,时间复杂度约为,远远快于试除法的
Miller-Rabin 素数判定算法整理
1. 核心原理
Miller-Rabin 算法是费马小定理与二次探测定理的结合,通过寻找“非平凡平方根”来从概率上判定一个数是否为合数。
A. 费马小定理 (基础检测)
如果 是素数,对于任意整数 (),满足:
- 局限性:存在“卡迈克尔数”(伪素数),它们是合数但能通过此测试。
B. 二次探测定理 (核心检测)
如果 是素数,且 ,则 的解只有两种可能:
- 推论:如果在模 的运算中,发现了一个数 ,它的平方是 1,但它自己既不是 1 也不是 ,则 必然是合数。
2. 证明
命题:若存在 满足 ,且 ,则 为合数。
证明步骤:
- 由 ,移项得 。
- 即 整除 ,记作 。
- 根据欧几里得引理 (Euclid’s Lemma):
- 如果 是素数,它必须整除 或者整除 。
- 即 或 。
- 反证:
- 如果我们发现 且 (即 ),说明 虽然整除乘积,却无法整除任何一个因子。
- 这违背了素数的性质(素数不可拆分)。
- 结论: 必然是合数。
3. 算法流程
假设要判定奇数 是否为素数。
第一步:拆解指数
将 提取出所有的因子 2,表示为: 其中 是奇数, 是非负整数。这一步是为了构建可以不断“开平方”的序列。
第二步:选取底数 (Witness)
选取一个(或多个)底数 () 进行测试。
- 注:在long long范围内 (),选取固定的 {2, 3, 5, 7,11,17,37} 这一组底数可实现百分百正确判定。
第三步:序列测试 (针对每一个 )
- 计算起点:算出 。
- 初步判断:
- 如果 或 ,则该底数测试通过(可能是素数),跳过后续步骤。
- 平方探测循环:
- 重复执行 次平方操作:。
- 在每次平方后检查:
- 若结果为 :测试通过(找到了 -1),停止本轮,判定为“可能是素数”。
- 若结果为 :判定为合数(触发二次探测定理,发现了非平凡平方根)。
- 最终审判:
- 如果循环结束, 仍未变成 ,说明最终 或者无法在最后一步前匹配到 -1。
- 判定为合数。
模板题
cin >> n;auto mul = [&](ll a, ll b, ll mod) { return (ll)((__int128)a * b % mod); };auto qp = [&](ll x, ll n, ll mod) { ll res = 1; while (n) { if (n & 1) res = mul(res, x, mod); x = mul(x, x, mod); n >>= 1; } return res;};auto MR = [&](ll x, ll d, ll r, ll p) -> bool { ll now = qp(p, d, x); for (int i = 0; i < r; i++) { ll tem = mul(now, now, x); if (tem == 1 && now != 1 && now != x - 1) return 0; // 最容易理解的写法 乘完变成1且原本不是1或-1 now = tem; } return now == 1;};vector<ll> primes = {2, 3, 5, 7, 11, 13, 17, 37};auto is_prime = [&](ll x) -> bool { if (x <= 3) return x == 2 || x == 3; if (x % 2 == 0) return 0; ll d = x - 1, r = 0; while (d % 2 == 0) { d >>= 1; r++; } for (auto p : primes) { if (p > x) continue; if (x == p) return 1; if (x % p == 0) return 0; if (!MR(x, d, r, p)) return 0; } return 1;};while (n--) { ll x; cin >> x; while (x++) { if (is_prime(x)) { cout << x << '\n'; break; } }}Miller-Rabin 素数判定算法整理
https://sanzenin.top/posts/obsidian/miller-rabin算法/分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ,距今已过 74 天
部分内容可能已过时