一.素数的定义
素数又称素数。一个大于 $1$ 的自然数，如果除了 $1$ 或者它本身之外，没有数字能被它整除，那么这个数就叫做素数。
二.素数的基础判断
大家都知道，对于素数判断，我们有一个时间复杂度为 $O(\sqrt{(n)})$ 的算法。
bool isprime (int n) {
for (int i = 2; i <= sqrt (n); i ++) {
if (n % i == 0) {
return false;
}
}
return true;
}
但是这个时间复杂度对于某些较大的数字无法通过。
这样，就诞生了一个更高效的素数判断方法：Miller Rabin。
三.费马小定理
若 $p$ 为素数，整数 $a$ 与 $p$ 互素，则 $a^ {p-1} \equiv 1\pmod p$。
我们设$d×2^{r}=p-1$，那么式子就转化为 $a^ {d · 2^ r} \equiv 1\pmod p$。
四.二次探测定理
若 $p$ 为素数，整数 $x<p$ ，那么对于 $x^ 2 \equiv 1 \pmod p$ 的解 $x$ 为 $1$ 或 $p - 1$。
证明：
上述式子可以化为 $x^ 2-1^ 2 \equiv 0 \pmod p$。
根据平方差公式：$a^ 2-b^ 2=(a+b)(a-b)$，
可以将上述式子化为： $(x+1)(x-1) \equiv 0 \pmod p$。
因为 $p$ 为素数，那么 $(x+1)(x-1) = 0$ 或 $(x+1)(x-1)$ 为 $p$ 的倍数。
那么，当 $(x+1)(x-1) = 0$ 时，显然 $x=1$。
当 $p∣(x+1)(x-1)$ 时，$x=p + 1$ 或 $x=p-1$。
由于 $x<p$，所以 $x=p + 1$ 不成立。
所以 $x=1$ 或 $x=p-1$。
两个定理结合起来，对于以下两个式子，最少有一个式子被满足：
五.$Miller Rabin$ 素数判断
$Miller Rabin$ 素数判断的过程如下：
将 $p-1$ 中的因子 $2$ 个数提取出来，先设 $d=p-1$，取
$k$ 个数 $1<a_ 1,a_ 2,a_ 3......a_ k<p$ 带入上述公式判断是否构成条件。
对于 $a$ 的个数，设一个适合的数字即可，在 $7-15$ 之间都可以，经过测试，取前 $k$ 个素数即可。
而这个算法对于 $long$ $long$ 范围之间的数的误差率几乎为 $0$。
时间复杂度为 $O(k \log p)$。
核心代码如下：
inline bool Miller_Rabin (ll n, ll a) {
ll d = n - 1, r = 0;
while (!(d & 1)) {//分解出所有的因子2。
r ++;
d >>= 1;
}
ll adn = ksm (a, d, n);
if (adn == 1) {//满足公式1。
return true;
}
for (int i = 0; i < r; i ++) {
if (adn == n - 1) {//满足公式2。
return true;
}
adn = mul (adn, adn, n); /不断乘2的i次幂。
}
return false;
}
