素性检验算法
确定性素性检验
Lucas 素性检验：
- 如果存在整数 a，使得 $$a^{n-1} \equiv 1 \pmod{n}$$，并且对 n-1 的任意素因子 p，$$a^{\frac{n-1}{p}} \not\equiv 1 \pmod{n}$$ 成立，那么 n 是素数。
Lehmer 素性检验：
- 如果对 n-1 的任意素因子 $$p_i$$，都存在一个整数 $$a_i$$，使得 $$a_i^{n-1} \equiv 1 \pmod{n}$$ 与 $$a_i^{n-1} \not\equiv 1 \pmod{n}$$ 成立，那么 n 是素数。
Pocklington 素性检验：
- 对 n-1 做不完全因子分解，得到 $$n-1 =mj$$，其中有标准分解式 $$m =p_1^{k_1}…p_r^{k_r}, m \ge \sqrt{n}, gcd(m, j) = 1$$。如果对于每个 $$p_i (1 \le i \le r)$$，都存在一个整数 $$a_i$$，使得 $$a_i^{n-1} \equiv 1 \pmod{n}, gcd(a_i^{\frac{n-1}{p_i} - 1}, n) = 1$$，那么 n 是素数。
随机性素性检验
引理：$$\displaystyle x^2 \equiv 1 \bmod{p} \Leftrightarrow x = \begin{cases} 1 & \bmod{p} \ -1 & \bmod{p}\end{cases}$$
确定性素性检测算法时间复杂度较高，大部分底层库中一般使用 Rabin-Miller 算法。
考虑下面的结论：
- 假设 p 是一个大于 2 的素数，于是 p-1 是一个偶数，设 $$p - 1 = 2^s * d$$，其中 s 是正整数，d 是奇数。
- 根据费马小定理，对于一个素数 p，我们有 $$a^{p-1} \equiv 1 \bmod{p}$$
- 对上式做开根号操作，我们有结论下者两式有一个成立 $$\begin{cases} a^d &\equiv 1 &\bmod{p} \ a^{2^r d} &\equiv -1 &\bmod{p} \text{ ,where }\exists r, 0 \le r \le s-1\end{cases}$$
上面结论的逆否命题是：
- 如果 $$\exists a \Rightarrow \begin{cases} a^d &\not\equiv 1 &\bmod{p} \ a^{2^rd} &\not\equiv -1 &\bmod{p} \text{, where } \forall r, 0 \le r \le s-1 \end{cases}$$，那么 p 是一个合数。
Rabin-Miller 算法利用上面结论的否命题进行判定，是一个不一定正确但是大概率正确的判定方式。
整数的分解
一、费马素数分解法
对于奇整数 n，能够获得一下的方程 $$n = x^2 - y^2$$ 的整数解，也就获得了 n 的两个因子，因为：$$n = (x - y)(x +y)$$
根据以上的结论，我们有以下的算法：
- 首先确定最小的整数 k，使得 $$k^2 \ge n$$，然后，对下面的数列：$$k^2 -n, (k+1)^2 - n, (k+2)^2 -n, …, ((n+1)/2)^2 - n$$ 按顺序进行测试，直到找到一个整数 m 使得 $$m^2 - n$$ 为一个平方整数，从而也就找到了一对因子。否则 n 就没有非平凡因子。
二、$$Pollad\ \rho$$ 分解算法
算法：
- 首先，确定一个简单的二次以上整系数多项式，例如 $$f(x) = x^2 + a, a\ne -2,0$$。然后，从一个初始值开始，利用迭代公式 $$x_{k+1} \equiv f(x_k) \pmod{n}$$ 计算一个序列 $$x_1, x_2, …$$。
- 令 d 为 n 的一个平凡因子，因为模 d 的剩余类个数比模 n 的剩余类个数少很多，很可能存在某个 $$x_i$$ 和 $$x_j$$ 是属于同一个模 d 剩余类又不属于模 n 的剩余类，所以 $$gcd(x_k - x_j, n)$$ 是 n 的非平凡因子。