Miller Rabin 质数判定
费马小定理
众所周知
当 \(p\) 是质数， 对于任意 \(a\)，有 \[a^{p - 1} \equiv 1 \pmod{p}\]
二次剩余
当 \(p\) 是质数，对于 \(x \in (0, p)\)，关于 \(x\) 的方程 \(x^2 \equiv 1 \pmod{p}\) 的解为 \(x = 1 \ or \ p\)。
两个逆定理同样成立。
下面开始正题
对于任意 \(a\)，令 \(p - 1 = 2^qm, m = 2n + 1, n \in \mathbb{N}\)： - 根据费马小定理，如果 \(a^{p - 1} \not\equiv 1 \pmod{p}\)，那么 \(p\) 不是质数； - 根据二次剩余，如果 \(a^{p} \equiv 1 \pmod{p}\) 但 \(a^{p - 1} \equiv 1 \pmod{p}\)，那 \(p\) 不是质数。
那么我们不断选择 \(a\) 进行检验。
如果 \(p\) 是质数，那么通过以上两个测试的概率为 \(1\)；如果 \(p\) 不是质数，那么通过以上两个测试的概率为 \(\frac{1}{4}\)。
只要取足够多个 \(a\)，那么就能将错误率降低到可以接受的范围内。
如果是 int 范围那么 \(10\) 次左右可以保证正确，如果是 long long 那么 \(20\) 次。
或者还有一种方法直接令 \(a\) 为前 \(10 \sim 20\) 个质数，至少 long long 范围内没有什么问题。
Pollar-Rho 分解质因数
名字来源可能是因为长得像 \(\rho\)？
网上的大部分资料都没怎么看懂，上来就是式子。
那我先放一张图。
好了讲完了 我是看了这张图突然明白的qwq
考虑在什么情况下能找到 \(p\) 的一个拆分。
这谁想的出来嘛
给出一个伪随机序列生成方式
\[a_i \equiv a_{i - 1}^2 + b \pmod{p}\]
这个数列的每一项都由前一项决定，且值域为 \([0, p)\)，那么数列 \(a\) 必然有循环节，也就是上面那个环。
我们把 \(p\) 换成 \(q\)，再生成一遍这个序列，又得到一个循环节。
设两次的循环节长度分别为 \(m\)、\(n\)，如果 \(m \not = n\)，那么说明我们找到了两个数 \(m, n\) 使得 \(\gcd(m - n, p) \not = 1 \ or \ p\)。
至于具体实现：
算出第一个序列，找到循环节长度 \(m\)；找到一个 \(q\)， 算出第二个序列，找到循环节长度 \(n\)。 然后分三类： - \(\gcd = 1 \ or \ p\)：再找 \(q\)； - \(\gcd \not = 1 \ or \ p\)：找到一个因子 \(\gcd\)。
于是我们完成了一次拆分。
下面来分析复杂度。
根据生日悖论，可得在第一个序列中出现相同数的期望长度为 \(\sqrt p\)，在第二个序列中出现相同数的期望长度为 \(\sqrt q\)。
那么只要枚举 \(\sqrt q\) 个数就可以找到一种拆分。
如果令 \(q\) 为 \(p\) 的最小因子，那么期望只要枚举 \(p^{\frac{1}{4}}\) 次。