Miller Rabin 学习小记

之前总结的时候写了一堆引理导致写的时候想不起来要干啥了，遂重新写一篇总结。

主要思想是逆用一下费马小定理，\(\forall x \in [1,p), x^{p-1} \equiv 1 \pmod p\)。

一个 naive 的想法是随机 \(x\)，直到 \(\text{gcd}(x,p) \gt 1 \or x^{p-1} \not \equiv 1 \pmod p\)，然而存在一系列数，使得所有与其互素的数后者都成立，这样的数有无穷多个。

此时再加入一个检测：\(x ^ 2 \equiv 1 \pmod p\) 的解只有 \(x \equiv \pm 1 \pmod p\)，证明考虑方程等价于 \(p | (x+1)(x-1)\)，若有非平凡解则推导出 \(p\) 的非平凡因子，矛盾。

于是对于待检测数 \(x\)，设 \(x - 1 = m2^k\)，这是假定 \(x\) 为质数有 \(\phi(x) = x-1\)，然后随机 \(u \in [2,x-2]\)，这是因为 \(-1,0,1\) 都是平凡的。

然后计算 \(v = u^{m} \bmod x\)，提取序列 \(v^2,v^4,v^8,\cdots,v^{2^k}\) 模 \(x\) 意义下的值，若 \(v^{2^k} \not \equiv 1 \pmod x\) 或者序列中 \(1\) 的前第一个非 \(1\) 值不是 \(-1\) 则判为合数，随机足够多组即可（一般为 \(8\)）。

注意 corner case。