Number Theory
Miller-Rabin 素性测试
引理1： 费马小定理
\(\forall p \in \mathbb P, 0 \le a \lt p, a^{p-1} \equiv 1 \pmod{p}\)
证明略。
引理2： 二次探测定理
\(\forall p \in \mathbb P, 0 \le x \lt p\)，方程 \(x ^ 2 \equiv 1 \pmod p\) 的解为 \(x \equiv \pm 1 \pmod p\)。
证明略。
设我们要检测的数为 \(n > 2\)。显然 \(n\) 为奇数，设 \(n - 1 = 2^s t\)，其中 \(t\) 为奇数。
若 \(n\) 为素数，我们希望 \(\forall a \in [1,n)\)，满足以下任意条件：
-
\(a^t \equiv 1 \pmod n\)。
-
\(\exists r \in [0,s), a ^ {2 ^ r t} \equiv -1 \pmod n\)。
Pollard-Rho 算法
推导
对于一个已知的合数 \(n>3\)，我们的目标是快速找到它的一个非平凡因子（除 \(1\) 和 \(n\) 外）。
显然问题可以转化为找到一个 \(k\) 使得 \(1 \lt \gcd(k,n) \lt n\)。
考虑一个序列 \(f\)，满足 \(f_0=0\) 且 \(f_i = (f_{i-1}^2 + c) \bmod n\)，其中 \(c\) 是常数。由生日悖论1得 \(f\) 中不同的数量的期望为 \(O(\sqrt n)\)。
设 \(m\) 是 \(n\) 的最小质因子，显然有 \(m \le \sqrt n\)。
设 \(g_i = f_i \bmod m\)，则 \(g\) 中不同的数量的期望为 \(O(\sqrt m)\)。
于是我们可以在期望 \(O(\sqrt m) \le O(n ^ {\frac 1 4})\) 的时间内找到两个位置 \(i,j\) 使得 \(f_i \not = f_j \land g_i = g_j\)，即 \(n \nmid (f_i - f_j) \land m \mid (f_i - f_j)\)，于是有 \(1 \lt m \le \gcd(|f_i - f_j|, n) \lt n\)
于是我们可以在期望 \(O(n ^ {\frac 1 4})\) 的时间内找到 \(k\) 满足 \(1 \lt gcd(k,n) \lt n\)，也就找到了一个 \(n\) 的非平凡因子。