核心概述
米勒–拉宾素性测试（Miller–Rabin）：快速判定整数是否为素数。通过将 n−1 写成 d·2^s，并检测若干底 a 的幂次是否落在 {1, −1} 模 n 的集合，从而以极低错误率（或在 64 位上用固定底实现确定性）给出素性判断。
原文引述
Description: Miller–Rabin primality test. Writes n−1 = d·2^s and checks a^d, a^{2d}, … modulo n for a small set of bases. Deterministic on 64-bit with a fixed base set; otherwise error probability ≤ (1/4)^k. Time: O(k · log n) modular exponentiations Status: tested
展开阐述
-
函数/接口（据实现）
- bool isPrime(u64 n)：返回 n 是否为素数。
- 内部依赖：
- mulmod(u128 / 自定义) 实现安全模乘（防溢出），见 090-数论-长整型模乘。
- powmod(base, exp, mod) 快速幂，见 091-数论-模幂。
- 底集合选择：
- 64 位确定性：使用少量固定底（实现内置），可对所有 2^64 范围内 n 判定正确。
- 通用概率版：随机选 k 个底，错误率 ≤ (1/4)^k。
-
核心算法
- 特判：n < 2 为合数；n 为 2/3 为素数；若 n 为偶数则合数。
- 写 n−1 = d · 2^s，d 为奇数。
- 对每个底 a：
- 计算 x ≡ a^d (mod n)。若 x1 或 xn−1，则此底通过。
- 否则重复 s−1 次：x = x^2 mod n；若 x==n−1 则通过；若最终均未命中 n−1，则判 n 为合数。
- 若所有底均通过，则判 n 为“可能素数”（在 64 位确定性底集合下即为素数）。
- 正确性基于强伪素数与二次剩余结构；合数通过概率至多 1/4 每底。
-
输出语义
- 返回 true 表示素数（概率/确定性取决于底集合）；false 表示合数。
-
复杂度
- 对每个底一次 powmod 和至多 s−1 次平方，整体 O(k · log n) 次模乘。
- 64 位固定底数量常数极小，实际极快。
-
使用与注意
- 模乘溢出：请用 __int128 或自定义 mulmod（见 090-数论-长整型模乘）。
- 底集合：实现中应选经证明的 64 位确定性底集合；若跨更大范围，需相应增补或转为概率法。
- 与分解联用：作为 084-数论-因数分解 的素性判定子程序；小因子可先试除（见 082-数论-埃拉托斯特尼筛、085-数论-快速筛）。