质数及素性判断
$61$ 是个质数来着；
$601$ 也是；
$202406011$ 也是。
记于 2024 年 6 月 1 日，儿童节
部分内容来自 OI-Wiki。
通常，我们在正整数上定义质数与合数：
若正整数 $p\lt 2$ 除了 $1$ 和 $p$ 没有其他正约数，那么称 $p$ 为质数（或素数、不可约数）。
若正整数 $a\gt 2$ 且 $a$ 不是质数，则称 $a$ 是合数。
质数有几个值得一提的性质：
- 对于合数 $a$，存在质数 $p\le\sqrt{a}$ 使 $p\mid a;$
- 所有大于 $3$ 的质数都可表示为 $6n\pm 1;$
- 质数有无穷多个。
另外，在 OI 领域，我们常将答案对质数取模；有时也用大质数作哈希模数。
我必须在此抱怨一句，不少人在取模数时简单的取自己的手机号或身份证号，我不是说这样不好，实际上我认为随机模数很好，只是这些数大都不是质数，哈希的冲突概率偏大，即使是随机数据也可能出现冲突，甚至多模数也难以补救。
现在技术已可以快速生成一组固定多模哈希冲突的数据1，不必大惊小怪，连 MD5 都已被破解，甚至可以制作可读的 MD5 冲突的 PDF。
这里公布一些常见质数，OI 赛制中请尽量避免使用它们作为哈希：
$10^5+3$, $2^{22}\times 5^2+1$, $2^{25}\times 5+1$, $2^{26}\times 7+1$, $2^{23}\times 7\times 17+1$, $10^9+7$, $10^9+9$, $2^{21}\times 479 + 1$, $2^{31}-1$, $2^{61}-1$, $10^{18}+3$.
而在 CF 这类赛制中，大多情况必须避免固定模数哈希2，必要时最好预先随机生成几百个大质数，每次用真随机数初始化梅森旋转，运行时随机选取五到六个质数。
设 $\pi(x)$ 表示小于或等于 $x$ 的质数的数量，随着 $x$ 的增大，有 $\pi(x)\sim\dfrac{x}{\ln x}$。
枚举 $(1,\sqrt{n}]$ 内的整数：
bool is_prime(long long n) {
for (long long p = 2; p * p <= n; ++p)
if (n % p == 0)
return false;
return true;
}
进一步地，为了优化常数，如果 $2\nmid n$，则无需尝试偶数；
更进一步地，由于大于 $3$ 的质数只能被表为 $6n\pm 1$，在试除 $2,3$ 后，只试除形如 $6n\pm 1$ 的数即可。
这种方法是 $O(\sqrt{n})$ 的。
如果 $n$ 的范围不大（如 $\le 2\times 10^8$），我们当然可以用筛法标记范围内所有质数，以便快速查询。
for (long long i = 2; i * i <= N; ++i)
if (!vis[i])
for (long long j = i * i; j <= N; j += i)
vis[j] = true;
这种方法是 $O(n)\sim O(1)$3 的。
那么，如果 $n$ 高达 $10^{18}$ 呢？高达 $10^{1000}$ 呢？
我们常用的算法是素性测试：
- 确定性测试：绝对确定一个数是否为素数。常见示例包括 Lucas–Lehmer 测试和椭圆曲线素性证明。
- 概率性测试：通常比确定性测试快很多，但有可能（尽管概率很小）错误地将合数识别为质数（反之不会）。而通过测试但实际上是合数的数字则被称为伪素数。有许多特定类型的伪素数，最常见的是费马伪素数，它们是满足费马小定理的合数。概率性测试的常见示例包括 Miller–Rabin 测试。
在 OI 领域，概率性测试更为普遍。
Fermat 测试基于著名的费马小定理，因此得名。
对于质数 $p$，若 $(a,p)=1$， $$a^{p-1}\equiv 1\pmod{p}.$$
证：只需证对任意 $a$ 和质数 $p$，$a^p\equiv a$ 成立。考虑归纳法：
显然 $1^{p}\equiv 1\pmod{p}$ 成立，假设对 $a\ge1$ 有 $a^p\equiv a$ 成立，则： $$\begin{aligned}(a+1)^p&\equiv a^p+\binom{p}{1}a^{p-1}+\binom{p}{2}a^{p-2}+\cdots +\binom{p}{p-1}a+1\\&\equiv a+1\pmod{p}\\&&\blacksquare\end{aligned}$$
不难想到，对于给定的 $n$，我们不断随机选取 $1\lt a\lt n$，检验是否 $a^{n-1}\equiv 1\pmod{n}$，若有一个不满足，则 $n$ 不是质数，否则，$n$ 大概率是一个质数。
做 $k$ 轮的时间复杂度为 $O(k\log n)$。
遗憾地是，这种判别方式正确率不高，事实上，存在一类合数 $n$，对所有 $(a,n)=1$，都有 $a^{n-1}=1$ 成立，这种数叫做 Carmichael 数。
容易证明，Carmichael 数有无穷个，$561=3\times 11\times 17$ 是最小的 Carmichael 数。
Miller–Rabin 素性测试是 Fermat 测试的改进，利用二次探测定理提高判定正确概率。
对于奇质数 $p$，$x^2\equiv 1\pmod{p}$ 的解只有 $x\equiv 1\pmod{p}$ 和 $x\equiv -1\pmod{p}.$
只需将方程移项，得 $(x-1)(x+1)=np$，由 $p$ 为奇质数，命题得证。
我们设 $n-1=u\times 2^t$，先计算 $a^u$，若其与 $1$ 同余，则通过本轮测试；否则，将其平方直到与 $a^{n-1}$，若结果不为 $1$ 或过程中未出现 $-1$，本轮测试不通过。
如此，我们得到一个较正确的素性测试：
bool millerRabin(int n) {
if (n < 3 || !(n & 1)) return n == 2;
if (n % 3 == 0) return n == 3;
int u = n - 1, t = 0;
while (!(u & 1)) u >>=1, ++t;
// test_time 为测试次数，建议设为不小于 8
for (int i = 0; i < test_time; ++i) {
// 无需检查 0, 1, -1
int a = rand() % (n - 3) + 2, v = quickPow(a, u, n);
if (v == 1) continue;
int s;
for (s = 0; s < t; ++s) {
if (v == n - 1) break;
v = (long long)v * v % n;
}
if (s == t) return false;
}
return true;
}
进行 $k$ 轮测试的时间复杂度为 $O(k\log n)$。
值得一提，若广义 Riemann 猜想（generalized Riemann hypothesis, GRH）成立，只需取 $[2,\min\{n-2,\lfloor2\ln^2 n\rfloor\}]$ 内所有整数测试即可确定 $n$ 的素性。那么，Miller–Rabin 测试可以看做一个多项式时间4内的素性判断算法。
在 OI 领域，我们通常对 $[1,2^{64})$ 内的数进行测试。对于 $[1,2^{32})$ 内的数，测试 $\{2,7,61\}$ 即可；对于 $[1,2^{64})$ 内的数，测试 $\{2, 325, 9375, 28178, 450775, 9780504, 1795265022\}$ 即可。
后者不好记，也可以改为 $\{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37\}$（前 $12$ 个质数）。
注意测试时要全取一遍，不能只选小于 $n$ 的。
另外，假设随机取 $k$ 个数作为基，那么错误的概率是 $4^{-k}$。
这里有一个 js 实现的高精度素性测试，使用至少 10 个随机数作为基底：
Number:Answer: is a Prime Number.
上文所述的取固定数作为基，可以看作 Miller-Rabin 测试的确定性变体，可以在 Deterministic variant of the Miller-Rabin primality test 了解更多信息。
如果认为多轮测试的常数太大，可以选择随机选取基数，不要选取已知基数的前几项，因为一旦已知或被猜到，容易选择强伪素数进行攻击。例如，假如选择前 $8$ 个质数（而不是前 $12$ 个），那么以下合数都能通过测试：
- $341550071728321 = 10670053 \times 32010157$
- $84983557412237221 = 206135341 \times 412270681$
- $230245660726188031 = 214831 \times 787711 \times 1360591$
- $1134931906634489281 = 753303361 \times 1506606721$
- $1144336081150073701 = 756417901 \times 1512835801$
- $1167748053436849501 = 764116501 \times 1528233001$
- $1646697619851137101 = 907385701 \times 1814771401$
- $3825123056546413051 = 149491 \times 747451 \times 34233211$
- $4265186605968234451 = 1032616411 \times 4130465641$
- $5474093792130026911 = 21319 \times 2238391 \times 114712159$
- $7033671664103127781 = 1875322861 \times 3750645721$
- $7361235187296010651 = 412339 \times 2061691 \times 8659099$
- $8276442534101054431 = 209431 \times 3560311 \times 11099791$
- $14688059738864848381 = 2709987061 \times 5419974121$
- $16043083915816662841 = 2832232681 \times 5664465361$
其中，$3825123056546413051$ 必须经过 $12$ 轮检验（即前 $12$ 个质数中只有 $37$ 认为它是合数）。
本文中记录的基数选择经过验证，可以确保正确，不要轻易选择其他固定的基数组合。
以上伪素数筛选自伪素数表，其中约有 $1.1\times 10^8$ 个质数。