算法简介
对一个数的素性测试有很多种做法，有确定性测试的算法，也有概率性测试的算法。
确定性素性测试算法
确定性素性测试这里介绍两种：
-
线性筛法：利用线性筛在 \(O(n)\) 的时间复杂度内，将一个范围内的数素性全部求出，然后 \(O(1)\) 查询。
-
试除法：在 \(\sqrt{n}\) 内试商，判定是否存在 \(> 1\) 的约数，时间复杂度 \(O(\sqrt{n})\)。
概率性素性测试算法
费马小定理的逆定理
费马小定理：对于一个素数 \(p\)，\(a^{p - 1} \equiv 1 \pmod p\)。
看到费马小定理，我们会想它的逆定理是否存在，如果存在，我们只需要随便选择一个 \(\le p\) 的数，然后进行判定即可。
但是，费马小定理的逆定理并不成立。素数一定满足费马小定理，但是有的合数也满足，如 \(341 = 31 \times 11,2^{341} \equiv 1 \pmod{341}\)。所以我们只能随机多个 \(\le p\) 的底数判定，才能有较高的概率得到正确的结果。
Miller-Rabin 素性测试
二次探测定理
对于奇素数 \(p\)，当 \(x\) 满足 \(x^2 \equiv 1 \pmod{p}\)，\(x\) 的解为 \(1,p - 1\)，我们将其称为平凡平方根。
这个结论的证明很简单，我们将 \(1\) 移项，然后用平方差公式展开，得到 \((x + 1)(x - 1) \equiv 0 \pmod{p}\)，我们发现要么 \(x - 1 = 0\)，要么 \(x = (-1) \bmod p = (p - 1) \bmod p\)。
二次探测定理的逆定理也是成立的。
Miller-Rabin
我们的 Miller-Rabin 算法就是结合费马小定理的逆定理和二次探测定理的逆定理进行素性测试。
设我们随机的底数为 \(a\)，我们先对 \(n \le 3\) 和 \(n\) 为偶数的情况特判掉。
对于奇数的 \(n\)，我们发现费马小定理的指数为 \(k = n - 1\)，此时 \(k\) 一定为偶数。我们改写为 \(k = 2^tv\)，先将 \(a\) 变为 \(a^v\)，如果此时 \(a = 1\)，我们可以认为 \(n\) 直接通过了本轮测试，原因显然。
然后我们把 \(a\) 进行 \(t\) 轮相乘，每次相乘，我们会得到一个结果 \(v\)。如果 \(v = n - 1\)，根据二次探测定理，我们找到了一个平凡平方根，可以通过测试。但是，如果我们在得到 \(n - 1\) 之前得到了 \(1\)，则说明我们找到了非平凡平方根，不符合二次探测定理的逆定理，测试失败。
如果我们进行了 \(t\) 轮相乘，仍然没有得到 \(n - 1\)，说明 \(n\) 一定为合数。至此，Miller-Rabin 算法结束。
标签：费马,定理,算法,测试,逆定理,素性 From： https://www.cnblogs.com/Feel-Good/p/18357910