Miller Rabin & Pollard's Rho

素性测试

二次探测定理：对于质数 $p$，方程 $x^2\equiv1\pmod p$ 的解只有 $x\equiv\pm1\pmod p$。

证明：$(x+1)(x-1)\equiv x^2-1\equiv1\pmod p$，于是 $p\mid(x+1)(x-1)$。由于 $p$ 是质数，$p\mid x+1$ 或 $p\mid x-1$ 至少有一个成立。$\square$

这意味着，如果我们想判定 $p$ 的素性，我们可以尝试找出 $x\not\equiv\pm1\pmod p$ 而 $x^2\equiv1\pmod p$ 的 $x$。一旦我们找出了一个这样的 $x$，$p$ 一定不是素数。而在经过大量检测后没有找到这样的 $x$，我们即宣称 $p$ 是素数（并且我们确实能够证明这样做的正确性）。

考察费马小定理 $a^{p-1}\equiv1\pmod p$，其中 $p$ 为素数。我们将 $p-1$ 表示为 $2^sd$，其中 $d$ 为奇数。

如果我们任选一个 $(0,p)$ 内的整数作为底数 $a$，将 $d,2d,4d,\cdots,2^{s-1}d$ 分别代入 $x$，如果有 $a^{2^kd}\not\equiv\pm1\pmod p$ 而 $a^{2^{k+1}d}\equiv1\pmod p$ 则说明 $p$ 不是质数。如果 $a^{p-1}\not\equiv1\pmod p$ 也说明 $p$ 不是质数。

可以证明，能够将一个非质数 $n$ 判别出来的底数 $a$ 至少有 $\left\lfloor\frac{n-1}2\right\rfloor$ 个。也即在 $(0,n)$ 中随机选取 $a$，将非质数判别为质数的概率不超过 $\frac12$，那么随机选择多个底数分别判断即可达到较高正确率。

如果广义黎曼猜想成立，只需以 $[2,\min\{n-2,\lfloor2\ln^2n\rfloor\}]$ 的所有数分别作为底数 $a$ 进行探测，即可确定 $n$ 的素性而不依赖于概率分析。而对于 OI 中常见的 $[1,2^{64})$ 中的所有数，只用不超过 $40$ 的 $12$ 个质数即可。

分解质因数

对于合数 $n$，通过枚举获取 $n$ 的因数是困难的，可以考虑以一定的方式生成一些 $k$，通过求 $\gcd(n,k)$ 获取 $n$ 的非平凡因子。那么我们要做的就是尽量减小 $\gcd(n,k)$ 为 $1$ 或 $n$ 的概率。

考虑数列 $a_0=0,a_i=(a_{i-1}^2+c)\bmod n$，其中 $c$ 是 $(1,n)$ 内的任意整数。设 $n$ 有某一因子 $k$。显然数列 $\{a_i\bmod k\}$ 一定会在有限项内进入循环。而 $a_i\bmod k=a_j\bmod k$ 意味着 $k\mid a_i-a_j$，此时如果 $n\nmid a_i-a_j$ 的话，$\gcd(n,a_i-a_j)$ 即为 $n$ 的一个非平凡因子，否则分解失败。

具体实现有两种。

第一种实现本质上是 Floyd 判环算法，从小到大枚举 $i$，如果某次 $k=\gcd(a_i-a_{2i},n)$ 不为 $1$，说明数列 $\{a_n\bmod k\}$ 在第 $i$ 项之前已进入循环。

第二种实现是利用倍增，将两个指针 $s,t$ 初始设为 $0$，第 $i$ 轮 $t$ 向后移动 $2^{i-1}$ 步，每步之后检查 $\gcd(n,s-t)$，该轮结束后将 $s$ 赋为 $t$。为了进一步优化常数，每 $127$ 步检验近 $127$ 步中 $s-t$ 的累乘结果。实验表明，$127$ 是一个很好的参数，过小会导致求 $\gcd$ 的次数较多，过大会导致累乘结果得到 $0$ 的概率过大，频繁失败。

两种实现的期望复杂度均为 $O(m\log a)$。其中 $m$ 为 $\min_{d|n}\#\{a_i\bmod d\mid i\in\mathbb N\}$ 在 $c$ 均匀随机时的期望。首先该值一定小于 $\#\{a_i\bmod k\mid i\in\mathbb N\}$，其中 $k$ 为 $n$ 的最小质因子。

那么期望多少项 $\{a_i\bmod k\}$ 会开始循环呢？首先我们发现该数列在 $(1,k)$ 内的分布较为均匀（这也是选择 $(x^2+c)\bmod n$ 来生成数列下一项的原因），所以该数列进入循环的项数等同于不断在 $k-1$ 个元素中均匀随机选取，第一次取到已经出现过的数的期望次数。

在 $n$ 个元素中进行 $t$ 次选择结果两两不同的概率为 $P=\prod_{i=0}^{t-1}\frac{n-i}n$，由 $1+x\le e^x$ 有

$$\displaylines{P=\prod_{i=0}^{t-1}\frac{n-i}n\le\prod_{i=0}^{t-1}\exp\left(-\frac in\right)=\exp\left(-\frac{t(t-1)}{2n}\right) }$$

于是对于 $p\in(0,1)$，

$$\displaylines{P\le p\Longleftarrow\exp\left(-\frac{t(t-1)}{2n}\right)\le p\iff t(t-1)\ge-2n\ln p\Longleftarrow t\ge\sqrt{-2n\ln p} }$$

将 $t$ 次选取看作一次实验，根据独立随机试验的结论，这样的实验失败一次的期望次数为 $\frac1{1-p}$，故在 $k-1$ 个元素中随机选取，直到得到相同元素的期望次数不超过

$$\displaylines{\frac1{1-p}\sqrt{-2(k-1)\ln p}=O(\sqrt k) }$$

于是该算法的复杂度为 $O(m\log a)=O(\sqrt k\log a)=O(\sqrt[4]n\log a)$。