Miller-Rabin 和 Pollard's Rho 算法

本文主要参考《数论概论》。

Miller-Rabin 素性测试

Miller-Rabin 素性测试是一种概率性的素性测试，换句话说，它可以给出合数证明。

首先有一个 naive 的想法就是观察费马小定理的逆否命题。

【定理 1】费马小定理：对于素数 $p$，有 $a^p \equiv a \pmod p$。

证明

那么如果 $a^b \not \equiv a \pmod b$ 则 $b$ 一定是合数。

一个合理的想法是多随机几组 $a$ 对数 $b$ 进行判断，这样如果 $b$ 是合数，应该就总能找到一个合数证明。

但是很不幸，有卡迈克尔数的存在导致这样的方法行不通。卡迈克尔数是一类合数 $n$，使得 $\forall a \perp n, a^n \equiv a \pmod n$。

例如 $561$ 就是一个卡迈克尔数。

而且卡迈克尔数非常多，无法特判掉（OEIS: A002997）。

那么就得换一种更强的方法了。

【定理 2】二次探测定理：若 $p$ 为奇素数，则 $a^2 \equiv 1 \pmod p \Rightarrow a\equiv 1 \pmod p$ 或 $a \equiv -1 \pmod p$。

证明 移项得到 $(a - 1)(a + 1) \equiv 0 \pmod p$。由于 $p$ 是素数，显然，$p \mid (a - 1)$ 或 $p \mid (a + 1)$。

【定理 3】：若 $p$ 为奇素数，令 $p - 1 = 2^kq$，且 $q$ 是奇数。设 $a$ 是不被 $p$ 整除的整数，则下述两个条件之一成立：

1. $a^q \equiv 1 \pmod p$
2. $a^q, a^{2q}, a^{2^2 q}, \ldots, a^{2^{k - 1} q}$ 之一模 $p$ 余 $-1$。

证明 由费马小定理，$a^{p - 1} \equiv 1 \pmod p$。因为 $p - 1 = 2^kq$，所以 $a^{2^kq} \equiv 1 \pmod p$。又因为 $a^q, a^{2q}, \ldots, a^{2^{k - 1}q}, a^{2^kq}$ 中每一个数都是前一个的平方，因此下述两种可能之一必定成立：

1. $a^q \equiv 1 \pmod p$，第一个条件成立。
2. 序列中有一些数模 $p$ 不余 $1$，但是平方之后模 $p$ 余 $1$。此时这个数模 $p$ 一定与 $-1$ 同余。在这种情况下，第二个条件成立。

这个定理的逆否命题就可以用来给出合数证明。

【定理 4】定理 3 的逆否命题：若 $n$ 为奇数，设 $n - 1 = 2^kq$，$q$ 是奇数。对于不被 $n$ 整除的某个 $a$，若下述两个条件均成立，则 $n$ 为合数：

1. $a^q \not \equiv 1 \pmod n$
2. $\forall i = 0, 1, 2, \ldots, k - 1, a^{2^iq} \not \equiv -1 \pmod n$

事实上，若 $n$ 是奇合数，则 $1$ 至 $n - 1$ 之间至少有 $75\%$ 的数 $a$ 可给出 $n$ 的合数证明。

因此，随机选取 $k$ 个 $a$ 对 $n$ 进行测试后没有一个数能给出合数证据，则 $n$ 仍然是合数的概率低于 $4^{-k}$，这已经非常小了。

事实上，对于 OI 而言，通常都是对 $[1, 2^{64})$ 范围内进行素性检验，这时有确定性的选取方法。对于 $[1, 2^{32})$ 范围内的数，选取 $\{2, 7, 61\}$ 三个数作为 $a$ 即可确定素性；对于 $[1, 2^{64})$ 范围内的数，选取 $\{2, 325, 9375, 28178, 450775, 9780504, 1795265022\}$ 七个数作为 $a$ 即可确定素性。

但是显然记不住这么多数。事实上，选取前 $12$ 个素数 $\{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37\}$ 也可以正确检验 $[1, 2^{64})$ 范围内的素数。

代码留坑待填。

Pollard’s rho 算法

留坑待填。