一道很有趣的论文题
目录传送门：cryptohack 练习学习汇总(writeup index)
Prime and Prejudice
简要分析：什么情况下 $a^{p-1}\bmod p\not=1$ 呢？是 $(a,p)\not=1$ 时，换而言之我们要构造一个合数 $p$ 能绕过 Miller Rabin 素性检验并传入其某一个因子作为 a
首先可以通过题目名字搜到一篇 2018 年的论文 Prime and Prejudice: Primality Testing Under Adversarial Conditions
这里给出一些可以下载这篇论文的链接：
问题的存在
首先这篇论文指出，我们常用的素数检验算法 Miller-Rabin 是一种概率性的算法。Miller-Rabin 的具体原理在此不进行赘述，可以在很多 OIer/ACMer 的博客里找到更详细的说明。具体而言，这个算法由若干次 base 不同的 Fermat 检验构成，而 Fermat 检验对于随意选定的一个 base 有一定概率把合数判断为素数。在大部分情况下，只要选定的基足够多，那么失误的概率便可以小到忽略不计。
但是，失误可能性的存在意味着，我们有机会构造出一个 $p_{false}$ 使得在某组特定的 basis 下被判断为合数（basis 已知）
错误的概率
如果 $n$ 能通过以 $a$ 为基的 Fermat 检验，那么我们称 $n$ 是基 $a$ 下的一个伪素数（pseudoprime）
同时，我们记 $S(a)$ 为以 $a$ 为基的 $1\sim a$ 之间的伪素数的个数，那么有
$\frac{1}{4}$ 的
换而言之，以 $a$ 为基的 Fermat 检验的失误概率最大为 $\frac{1}{4}$，这进一步证明了上面的这一句话
在大部分情况下，只要选定的（用于 Fermat 检验的）基足够多，那么（Miller Rabin 算法）失误的概率便可以小到忽略不计
Carmic-heal 数
论文的 2.1 节给出了定理 Korselt’s Criterion
Theorem 2 (Korselt’s Criterion). A positive composite integer n is a Carmic-hael number if and only if n is square-free, and p − 1 | n − 1 for all prime divisors p of n.
首先要知道 Carmic-heal 数的定义。Carmic-heal 指的是这样一类数，对所有的 $1<a<n,n\not|a$ 的 $a$ 满足 $a^{n-1}\equiv 1\pmod n$。可以发现这些数完完全全地通过了 Fermat 检验。一个比较小的 Carmic-heal 数是 $561=3\times 11\times 17$（一些其他性质：必然为奇数，至少拥有 3 个质因子）
翻译一下，Theorem 2 讲的是，$n$ 是 Carmic-heal 数当且仅当 $n$ 的因子中不含除了 1 之外的平方数，且对于所有的 $p|n$ 有 $p-1|n-1$
我们最终要构造的也是这样的一个 Carmin-heal 数
伪素数的构造
在 3.1 节中论文提到
In empirical work, Pomerance et al. [PSW80] showed that many composite numbers that pass a Miller-Rabin primality test have the form n = (k + 1)(rk + 1) where r is small and both k + 1 and rk + 1 are prime.
也就是说，很多的能通过 Miller-Rabin 检验的数都形如 $(k+1)(rk+1)$，其中 $r$ 比较小且 $k+1,rk+1$ 都是素数
随后，注意到这题使用的是固定 basis，所以将目光锁定到论文的 3.1.2 节，随后直接跳转到附录 A
Arnault Method 会生成一个 $n=p_1p_2\cdots p_h$，其中 $p_i$ 是不同的奇素数且 $n$ 是素数基 ${a_1,a_2,\dots,a_t}$ 所对应的伪素数。易知 $k\ge 3$（Carmic-heal 数的性质）
这个算法首先选定一个 $p_1$，然后对于 $2\le i\le h$ 有 $p_i=k_i(p_1-1)+1$，其中 $k_i$ 由我们选定（应为质数且模 4 余 3）
事实上，选定 $p_1$ 的过程就是最难的点。
下面简要介绍了算法流程，正确性的证明略去，可以在论文中找到更详细的说明
- 首先，算法生成了 $S_a$，$S_a[a]$ 记录了素数 $a\in basis$ 对应的所有的满足 $\left(\frac{a}{i}\right)=-1$ 的 $i$ 模 $4a$ 的值
- 然后是 $S_b$。考虑到需要有 $k_i(p_1 − 1) + 1 \in S_a$，改写为找出符合条件的 $p_1$ 后，放入 $S_b[a]$ 中
- 枚举所有的可能的 $S_b[a]$ 构成的组合（itertools.product），对于每一个求 exCRT 合并得到结果（模数为 $4a$）。注意这里要有额外的 CRT 方程，为 $(-k_2^{k_1}, k_1)$ 和 $(-k_1^{k_2}, k_2)$
- 然后就可以得到 $p_1=k\cdot mod+res$，在合理范围内计算出 $p_1$ 及对应的其他 $p_i$ 并检验，可以获得结果
代码: cryptohack/mathematics primes Prime-and-Prejudice.py
代码中有一个封装好的类，可以直接使用