素数判定
cancan123456
·
·
个人记录
算法一
我会试除法！
注意到如果 n 是合数，那么其最小因子一定小于等于 \lfloor\sqrt n\rfloor，因此可以枚举 1\sim\lfloor\sqrt n\rfloor 中的所有整数 i，判断 i 是不是 n 的因子，时间复杂度 O(\sqrt n)。
算法二
我会 Miller-Rabin！
考虑费马小定理：
设 p 是任意质数，则对于所有 1\le a<p 都有 a^{p-1}\equiv1\pmod p。
那么，假设我们拿到一个数 n，可以随机几个 a，然后计算 a^{n-1}\bmod n 是不是 1，如果都是 1，那么说明 n 有可能是素数。
但是有个小问题，有一些合数 n 也满足对于所有 1\le a<n，a^{n-1}\equiv1\pmod n，其中，最小的 n 是 n=561，这些数被称为 Carmichael 数，或称为费马伪素数。
再考虑二次探测定理：
设 p 为任意奇素数，则 x^2\equiv1\pmod p 的解为 x\equiv\pm1\pmod p。
结合费马小定理，我们可以得到 Miller-Rabin 算法：
- 设随机选了一个 a（貌似选质数效果更好）。
- 对 n-1 进行分解，分解的形式为 2^td。
- 计算 u=a^d，不断平方，得到 a^{2d},a^{4d},\cdots,a^{2^td}=a^{n-1}。
- 对 a^{2d},a^{4d},\cdots,a^{2^td}=a^{n-1} 使用二次探测定理验证。
- 计算到最后会得到 a^{n-1}，直接判断其是不是 1 即可。
另外注意特判 1 和 a=0 的情况。
时间复杂度为 O(\text{你选择的 }a\text{ 的个数}\log n)，其中把乘法视作 O(1)。
还有，如果你选前 7 个质数，那么最小反例是 341550071728321\approx3.7\times10^7。
可以证明，如果 n 不是质数，那么在 2\sim n-1 范围内至少存在 \dfrac34 的数能够判断 n 不是质数，因此，如果你随机选择 k 个 a，那么该算法的正确率为 1-\left(\dfrac14\right)^t。
另外说一句，据 P4718 第三篇题解，如果你选择前 12 个质数，那么在 2^{78} 范围内都能够正确判断。
还有，如果 GRH 成立，那么选取 1\sim2\lfloor\log^2_2n\rfloor 的所有数作为 a，就能够判断 n 是不是素数，时间复杂度为 O(\log^3n)。
算法三
我会使用 Lucas 序列判断！
定义 Jacobi 符号 \left(\dfrac an\right)，有时也写作 (a|n)：设 n 的质因数分解为：
n=\prod_{i=1}^kp_i^{a_i}
则
\left(\frac an\right)=\prod_{i=1}^k\left(\frac a{p_i}\right)^{a_i}
其中 \left(\dfrac ap\right) 为 Legendre 符号，定义为 \left(\dfrac ap\right)=a^{\frac{p-1}2}。
定义 Lucas 序列 U_k(P,Q),V_k(P,Q) 为：
U_0(P,Q)=0
U_1(P,Q)=1
U_n(P,Q)=P\cdot U_{n-1}(P,Q)-Q\cdot U_{n-2}(P,Q)
V_0(P,Q)=2
V_1(P,Q)=P
V_n(P,Q)=P\cdot V_{n-1}(P,Q)-Q\cdot V_{n-2}(P,Q)
显然可以矩阵快速幂计算。
不知道谁证明了如下结论：给定 P,Q，令 D=P^2-4Q，则如果 n 是素数，我们有：
U_{n-(D|n)}(P,Q)\equiv0\pmod n
考虑其逆否命题，即如果存在 P,Q 使得
U_{n-(D|n)}(P,Q)\not\equiv0\pmod n
则 n 不是质数。
选择一个 D 使得 \left(\dfrac Dn\right)=-1，则第一个同余式变为：
U_{n+1}(P,Q)\equiv0\pmod n
如果其错误，那么 n 一定不是质数。
如果其正确，那么 n 有可能是质数，这样的数被称作 Lucas 可能素数（原文 Lucas probable prime）。
可能你已经听懵了，我们举个例子（抄的 wikipedia 的）：
- 一个 n 是质数的例子。
写个小程序得到 $U_{20}(3,-1)=6616217487$，而 $6616217487=19\times348221973$，所以我们有：
$$U_{n-(D|n)}\equiv0\pmod n$$
2. 一个 $n$ 是合数的例子。
$n=119=7\times17$，仍然取 $P=3,Q=-1$，这时 $D=13$，通过一些计算可以得到 $\left(\dfrac Dn\right)=-1$，所以我们要计算 $U_{120}(3,-1)$ 是多少。
计算得到 $U_{120}(3,-1)=51111310645837869275452942374954222245112848505020769456832800$，是 $19$ 的倍数，所以：
$$U_{n-(D|n)}\equiv0\pmod n$$
但是 $n$ 不是质数，这就说明了 Lucas 素性测试不能判断一个数是不是素数。
如果你取 $P=1,Q=-1$，即 Fibonacci 数列，那么最小的反例是 323，次小反例为 377。
下面介绍强 Lucas 素性测试。
设 $\delta(n)=n-\left(\dfrac nD\right)$，将 $\delta(n)$ 分解为 $2^td$ 的形式，其中 $d$ 是奇数，那么对于任意质数 $n$ 我们有下面两个条件必满足其一：
$$U_d(P,Q)\equiv0\pmod n$$
$$V_{2^rd}(P,Q)\equiv0\pmod n$$
对于至少一个 $0\le r<s$。
那么怎么选 $P,Q$ 呢？
通常在序列 $5,-7,9,-11,13,\dots$ 中选择第一个满足 $\left(\dfrac nD\right)=-1$ 的数，然后取 $P=1,Q=\dfrac{1-D}4$。
实现细节：
首先判断 $n$ 是偶数，$n$ 是完全平方数的情况。
然后在 $5,-7,9,-11,13,\dots$ 中选取第一个满足 $\left(\dfrac Dn\right)=-1$ 的 $D$，然后令 $P=1,Q=\dfrac{1-D}4$。
如果 $n$ 是一个完全平方数，那么你永远也找不到一个 $D$。
如果这样选择 $P,Q,D$，那么前 10 个强 Lucas 伪素数是：
5459，5777，10877，16109，18971，22499，24569，25199，40309，58519。
时间复杂度为 $O(\log^3n)$。
两个例外：
通常将强 Lucas 素性测试与 $a=2$ 的 Miller-Rabin 素性测试结合在一起，称为 Baillie–PSW 素性测试，目前没有发现反例。
## 算法四
我会 APR-CL 算法！
原始论文：[APR 算法](https://www.ams.org/journals/mcom/1984-42-165/S0025-5718-1984-0726006-X/S0025-5718-1984-0726006-X.pdf)，[APR-CL 算法](https://www.ams.org/journals/mcom/1987-48-177/S0025-5718-1987-0866102-2/S0025-5718-1987-0866102-2.pdf)。
还有个日语材料：[点这里](https://wacchoz.hatenablog.com/entry/2018/12/16/155500)。
试图翻译：
注：日语里的 Dirichlet 指標指的是 Dirichlet 特征。
首先定义 Dirichlet 特征与高斯和。
乘法群 $(\mathbb Z/p\mathbb Z)^\times$ 到非零复数的乘法群 $\mathbb C^\times$ 的群同态 $\chi:(\mathbb Z/p\mathbb Z)^\times\rightarrow\mathbb C^\times$ 被称为模 $p$ 意义下的 Dirichlet 特征。
用人话来说，就是定义一个函数 $\chi:\mathbb Z/p\mathbb Z\rightarrow\mathbb C$，满足：
$$\chi(ab)=\chi(a)\chi(b)$$
$$\chi(a)\begin{cases}=0&\gcd(a,p)\not=1\\\not=0&\gcd(a,p)=1\end{cases}$$
设 $g$ 是 $p$ 的一个原根，则对于任意 $0<a<p$ 都有：
$$a\equiv g^x\pmod p$$
其中 $0<x<p-1$，令 $\operatorname{ind}a=x$，就像 $\left(\log_ga\right)\bmod p$。
设 $q$ 是 $p-1$ 的一个质因子，$q^k\mid(p-1),q^{k+1}\nmid(p-1)$，令：
$$\zeta_{q^k}=e^{\frac{2\pi i}{q^k}}$$
显然，$\zeta_{q^k}$ 为一个单位根。
于是我们便有：
$$\chi(a)=(\zeta_{q^k})^{\operatorname{ind}a}$$
这就是一个 Dirichlet 特征。
或者你也可以这么写：
$$\chi(g^x\bmod q)=(\zeta_{q^k})^x$$
按照 $\chi$ 的定义，我们有：
$$\chi(ab)=\chi(a)\chi(b)$$
不难验证其成立。
现在，我们定义高斯和（标准符号应该是 $G(\chi)$，不过原文用的 $\tau(\chi)$）为：
$$\tau(\chi)=\sum_{x\in(\mathbb Z/p\mathbb Z)^\times}\chi(x)\zeta_p^x$$
显然，以下两个等式成立：
$$\zeta_p^0+\zeta_p^1+\zeta_p^2+\cdots+\zeta_p^{p-1}=0$$
$$\zeta_{q^k}^0+\zeta_{q^k}^{q^{k-1}}+\zeta_{q^k}^{2q^{k-1}}+\cdots+\zeta_{q^k}^{(p-1)q^{k-1}}=0$$
那么 Gauss 和可以表示为：
$$\tau(\chi)=\sum_{i=0}^{(q-1)q^{k-1}}\sum_{j=0}^{p-2}a_{i,j}\zeta_q^i\zeta_p^j$$
其中 $a_{i,j}$ 在 $\bmod n$ 意义下唯一。
为了进一步说明，先令 $t=5040=2^4\times3^2\times5\times7$，那么有很多素数 $p$ 使得 $p-1$ 是 $t$ 的因子，比如 $11,13$ 和 $47$。
然后令 $e(t)$ 为这些 $p$ 的乘积：
$$e(t)=2\prod_{p\in\mathbb P,(p-1)|t}p^{v_p(t)+1}$$
我也不知道前面的 $2$ 是从哪来的。
其中，$v_p(t)$ 表示 $p$ 在 $t$ 的质因子中出现了几次，比如 $v_2(12)=2$。
那么有：
$$\begin{aligned}e(5040)&=2^6\times3^3\times5^2\times7^2\times11\times13\times17\times19\times29\times31\times37\times41\times43\times61\times71\times73\times113\times127\times181\times211\times241\times281\times337\times421\times631\times1009\times2521\\&=15321986788854443284662612735663611380010431225771200\\&\approx1.52\times10^{52}\end{aligned}$$
其将可以测试满足 $n<e(t)^2$ 的数是不是素数。
假设我们已经找到了一个 $t$ 满足 $n<e(t)^2$，然后我们计算 $\gcd(n,t\cdot e(t))$，如果其不为 $1$，证明我们找到了一个因子，否则，我们可以知道 $n$ 的质因子不是很小。
设 $p$ 是 $e(t)$ 的一个质因子，$p^k\mid e(t),p^{k+1}\nmid e(t)$，那么，如果 $n$ 是一个素数，那么有：
$$\begin{aligned}\tau(\chi)^n&\equiv\left(\sum_x\chi(x)\zeta_p^x\right)^n\\&\equiv\sum_x\chi(x)^n\zeta_p^{nx}\\&\equiv\frac1{\chi(n)^n}\sum_{x}\chi(nx)^n\zeta_p^{nx}\\&\equiv\frac1{\chi(n)^n}\sum_x\chi(x)^n\zeta_p^x\\&\equiv\frac1{\chi(n)^n}\tau(\chi^n)\pmod n\end{aligned}$$
所以我们得到了：
$$\tau(\chi)^n\equiv\frac1{\chi(n)^n}\tau(\chi^n)\pmod n$$
那么，如果在所有 $p,q$ 的组合中，有一个使得该同余式不成立，那么 $n$ 一定不是素数。
但是，如果在所有 $p,q$ 的组合中，所有同余式都成立，我们也不能说 $n$ 是质数。
中间一通分析得到其计算量约为 $10^{10}$。
所以我们将其改写为 Jacobi 和的形式。
定义两个 $\bmod p$ 意义下的 Dirichlet 特征 $\chi_1,\chi_2$ 的 Jacobi 和为：
$$j(\chi_1,\chi_2)=\sum_{x=2}^{p-1}\chi_1(x)\chi_2(1-x)$$
这样计算量会小一点，具体来说，当 $q^k=2^4$ 时计算量最大。
定义 $\chi_0$ 为一个 $\bmod p$ 意义下的 Dirichlet 特征使得 $\chi_0(x)=[\gcd(x,p)=1]$。
Jacobi 和具有如下性质：
设 $\chi\not=\chi_0$ 是一个 $\bmod p$ 意义下的 Dirichlet 特征，有：
$$\tau(\chi)\tau(\bar\chi)=\chi(-1)p$$
$$|\tau(\chi)|=\sqrt p$$
设 $\chi_1,\chi_2$ 是两个 $\bmod p$ 意义下的 Dirichlet 特征，如果满足 $\chi_1\chi_2\not=chi_0$，有：
$$j(\chi_1\chi_2)=\frac{\tau(\chi_1)\tau(\chi_2)}{\tau(\chi_1\chi_2)}$$
定义：
可是这个复杂度十分的不像人样。
设 $\chi_1,\chi_2$ 是两个 $\bmod p$ 意义下的 Dirichlet 特征且 $\chi_1\chi_2\not=\chi_0$，那么有：
$$j(\chi_1,\chi_2)=\frac{\tau(\chi_1)\tau(\chi_2)}{\tau(\chi_1\chi_2)}$$
当 $\gcd(a,n)=1$ 时定义 $\sigma_a$ 为 $\sigma_a(\zeta_n)=\zeta_n^a$（$\sigma_a\in\operatorname{Gal}(\mathbb Q(\zeta_n))/\mathbb Q$）。
定义 $G=\{\sigma_a:\gcd(a,n)=1,\sigma_a(\sigma_n)=\sigma_n^a\}$，即所有 $\sigma_a$ 的集合。
## 算法五
我会 ECPP 算法！
[看这里](https://en.jinzhao.wiki/wiki/Elliptic_curve_primality)
可是这是期望复杂度。
## 算法六
我会 AKS 算法！
根据目前已证明的定理，其时间复杂度 $O^\sim(\log^{10.5}n)$，其中 $O^\sim(t(n))=O(t(n)\operatorname{poly}(\log t(n)))$，如果 Sophie Germain 素数密度猜想或者 Artin 猜想成立，那么其时间复杂度为 $O^\sim(\log^6n)$。
其具有以下四个特点：
1. 通用性。
2. 时间复杂度不是期望。
3. 不依赖未证明的猜想。
4. 保证正确。
之前的素性测试算法最多能满足其上的三个，Miller-Rabin 不满足保证正确或者不依赖未证明的猜想，Lucas 序列不保证正确，ECPP 是期望时间复杂度，APR-CL 算法时间复杂度 $(\log n)^{O(\log\log\log n)}$，还有一堆奇奇怪怪的方法仅对特殊的数有效。
提出这个算法的论文的标题是：
$$\LARGE\text{PRIMES is in P}$$
表示判断素数有了一个确定性的多项式级别的时间复杂度算法。
首先有一个定理：如果 $n$ 是整数，$a$ 与 $n$ 互质，则 $n$ 是素数当且仅当
$$(x+a)^n\equiv x^n+a\pmod n$$
这是该文章的第一个引理。
一个想法是枚举 $a$，依次判断该等式是否成立，但是时间复杂度太高了。
考虑设置一个 $r$，然后让两边同时对 $x^r-1$ 取模，即：判断如下等式是否成立：
$$(x+a)^n\equiv x^n+a\pmod{x^r-1,n}$$
然后测试一些 $a$，看上面的等式是否成立，具体来说，算法流程是：
1. 判断 $n$ 是否是 $a^b,b\not=1$ 的形式。
2. 暴力找到一个最小的整数 $r\ge2$ 使得 $\delta_r(n)>\log_2^2n$。
3. 暴力判断 $[2,r]$ 中的每一个数是不是 $n$ 的因子。
4. 如果 $n\le r$，则 $n$ 是质数。
5. 枚举 $\left[1,\left\lfloor\sqrt{\varphi(r)}\log_2n\right\rfloor\right]$ 中的所有整数 $a$，判断 $(x+a)^n\equiv x^n+a\pmod{x^r-1,n}$，如果不成立，返回合数，否则，返回素数。
> 关于 $\delta_r(n)$：
> 这个记号是阶，有的时候也记作 $\text{ord}_r(n)$，表示满足 $n^x\equiv1\pmod r$ 的最小正整数 $x$。
注意：大整数的加减和比较运算都是 $O(\log\max\{a,b\})$ 的，模乘是 $O(\log\text{mod})$ 的。
你可能觉得找 $r$ 的算法有点暴力，实际上，我们有：
$$\exists r\le\max\left\{3,\left\lceil\log_2^5n\right\rceil\right\},\delta_r(n)>\log_2^2n$$
所以可以暴力枚举 $r$，然后判断是否对于每一个 $1\le k\le\log_2^2n$，都有 $n^k\not\equiv1\pmod r$。
所以，可能 $r$ 一共有 $O(\log_2^5n)$ 个，判断需要 $O(\log_2^2n)$，其时间复杂度为 $O(\log_2^7n)$。
第三步是 $O(r\log n)=O(\log_2^6n)$ 的。
第四步是 $O(\log n)$ 的。
第五步，判断每个方程是否成立，时间复杂度为 $O^\sim(r\log_2^2n)$，所以总时间复杂度为：
$$O^\sim(r\sqrt{\varphi(r)}\log_2^3n)=O^\sim(r^{3/2}\log_2^3n)=O^\sim(\log_2^{10.5}n)$$
所以算法的总时间复杂度为：
$$O^\sim(\log_2^{10.5}n)$$
注意其空间复杂度 $O(\log^3n)$。
这证明了一个结论：判断素数是一个 P 问题。
代码部分：
```cpp
// Miller-Rain
const int pcnt = 12;
const ll prime[pcnt] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
bool Miller_Rabin(ll n, ll a) {
ll d = n - 1, t = 0;
while ((d & 1) == 0) {
d /= 2;
t++;
}
ll u = pow(a, d, n);
for (int i = 0; i < k; i++) {
if (u * u % n == 1 && now != 1 && now != n - 1) {
return false;
}
u = u * u % n;
}
if (u != 1) {
return false;
} else {
return true;
}
}
bool is_prime(ll n) {
if (n == 1) {
return false;
}
for (int i = 0; i < pcnt; i++) {
if (n == prime[i]) {
return true;
}
if (n % prime[i] == 0) {
return false;
}
if (!Miller_Rabin(n, prime[i])) {
return false;
}
}
return true;
}
```