Miller-Rabin 可以帮助我们快速判断一个大数是不是质数,现在已经有了确定性算法。在 \(2^{64}\) 范围内,我们可以快速地进行确定性判素。
二次校验定理:若 \(p\) 为奇质数,则 \(a^x \equiv 1 \pmod p\) 的解为 \(x = ±1\)。
我们有这样的流程:
令 \(d = p - 1\),然后不断检验 \(a^d\),并令 \(d \leftarrow \dfrac{d}{2}\),直到 \(d\) 为奇数(注意这时要再检验一次)。
容易想到,我们可以随机一些 \(a\) 并对其进行判断。可以证明的是,取前 12 个质数作为 \(a\) 进行校验就可以在 \(2^{64}\) 的范围内的确定一个数的素性了。
Pollard-Rho 可以帮助我们快速求出一个合数 \(n\) 的质因子。它采用随机算法,
一开始时,\(t = 0\),然后每次让 \(t \leftarrow t^2 + c\;\text{mod}\;p\),其中 \(c\) 为一个随机的常数。
这样得到的一群随机数会成环,样子很像 rho,所以得名 Pollard-Rho。
我们假设 \(n\) 最小的质因子为 \(m\),若连续两次生成的 \(t\) 的差的绝对值在模 \(m\) 意义下的值相同,那么这个差和 \(n\) 的 gcd 就是一个 \(n\) 的非平凡因子,由生日悖论,需要的 \(t\) 的个数是 \(O(\sqrt{m})\) 的,也就是 \(O(n^{\frac{1}{4}})\) 的,因为 \(m \leq \sqrt{n}\)。
为了优化这个过程,我们采用倍增法,即枚举步长,在每段结尾算一遍 \(\prod |t_i - t_0|\) 与 \(n\) 的 gcd,并在每个步长的过程中每 \((2^k - 1)\) 次生成 \(t\) 后求一遍 gcd,这里一般取 \(k = 7\)。
如果 gcd > 1,那么我们就成功找到了 \(n\) 的一个非平凡因子,直接返回其值即可。
标签:gcd,Miller,质数,Pollard,Rho,Rabin From: https://www.cnblogs.com/abcdeffa/p/18286519