2023-05-08

[WP] cryptohack mathematics primes

一道很有趣的论文题

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$ 之间的伪素数的个数，那么有

S(n)\le\frac{\varphi(n)}{4}

$\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\bmod 4a\in\bigcap_{i=1}^{h}k_i^{-1}(S_a+k_i-1)$ 找出符合条件的 $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

代码中有一个封装好的类，可以直接使用