数论——Fermat素性检验、Miller-Rabin素性检验
试除法与素性测试
试除法：所有的试除法，无论是 \(\mathcal O(n)\) 的还是 \(\mathcal O(\sqrt n)\) 的，其本质都相同：
- 即找 \(n\) 可能存在的因子 \(k\)，判断 \(k \mid n\)。
素性测试：旨在不用分解因数的方式，判断一个数是否为质数；素性测试分为两种：
- 确定性测试：（绝对正确的）确定一个数是否为素数。
- 概率性测试：具有较高正确率，但是不完全保证准确。
Fermat 素性检验
我们知道有费马小定理：\(a^{p-1} \equiv 1 \pmod p\)（\(p \in \mathbb P,a \perp p\)）。
据此，我们得出费马小定理的逆否命题：
若有 \(a \perp p\) 且 \(a^{p - 1} \not\equiv 1 \pmod p\)，则 \(p\) 一定不是质数。
但是逆否命题不意味着逆命题成立，因此，满足上一命题的，不一定完全是质数。
此类满足费马小定理逆否命题，但不是质数的数，称为 Carmichael 数。
在大部分情况下，我们使用（并不正确的）费马小定理逆定理，判定一个质数。
这个过程称为 Fermat 素性检验。
二次探测定理
如果 \(p\) 是奇质数（只有质数 \(2\) 不是奇质数），则:
\(x^2 \equiv 1 \pmod p\) 的解为 \(x \equiv 1 \pmod p\) 或 \(x \equiv p-1 \pmod p\)。
证明：
\[\begin{array}{rcl} x^2 &\equiv& 1 \pmod p\\ x^2-1 &\equiv& 0 \pmod p\\ (x+1)(x-1) &\equiv& 0 \pmod p\\ \end{array} \]因此 \(x \equiv 1 \pmod p\) 或 \(x \equiv p-1 \pmod p\)。
Miller-Rabin 素性检验
Miller–Rabin 素性测试是根据费马测试和二次探测定理优化得到的。
其准确性较高，目前已知没有通过 Miller–Rabin 素性测试而非质数的。
因此我们可以（在 OI 中）放心使用。
其复杂度为 \(\mathcal O(k \log^3 n)\)，表示对 \(n\) 进行 \(k\) 次测试。
思想：
将 \(a^{p-1} \equiv 1 \pmod p\) 中的指数 \(p−1\) 分解为 \(p−1=u \times 2^t\)。
对随机出来的 \(a\) 先求出 \(v = a^{u} \bmod n\)，之后对这个值执行最多 \(t\) 次平方操作。
若发现非平凡平方根时即可判断出其不是素数，否则再使用 Fermat 素性测试判断。
代码：
using ll = long long;
ll qpow(ll a, ll b, ll p) {
ll r = 1;
for (; b; b >>= 1) {
if (b & 1) r = r * a % p;
a = a * a % p;
} return r;
}
bool Miller_Rabbin(ll a, ll n) {
ll s = n - 1, r = 0;
while ((s & 1) == 0) s >>= 1, ++r;
ll k = qpow(a, s, n);
if (k == 1) return true;
for (int i = 0; i < r; ++i) {
if (k == n - 1) return true;
k = k * k % n;
} return false;
}
bool isPrime(ll n) {
if (n <= 1) return false;
ll times = 7;
ll primes[100] = {2, 3, 5, 7, 11, 233, 331};
for (int i = 0; i < times; ++i) {
if (n == primes[i]) return true;
if (!Miller_Rabbin(primes[i], n)) return false;
} return true;
}