Miller-Rabin 素性检验本身是一种概率性的素性检验方式，作为一种随机化算法，它能够在短时间内判断一个数是否为素数（一定概率下还是会出错的）。

# Fermat 素性检验

一个简单的素性判定思路是使用 Fermat 小定理：

对于整数 $a$ 和素数 $p$ ，有
$a^{p-1}\equiv 1 (mod\ p)$

对于我们任意选取的整数 $a$ ，如果 $p$ 是一个质数，那么肯定是满足 $a^{p-1}\equiv 1 (mod\ p)$ 的。如果我们选取了足够多的 $a$ 并且都经过了验证，那我们可以认为 $p$ 非常有可能是一个素数。

	def fermat_primality_test(p, k = 40):
	for _ in range(k):
	a = random.randint(2, p)
	if pow(a, p - 1, p) != 1:
	return False
	return True

然而问题在于，Fermat 小定理的逆命题不一定成立，也就是说 Fermat 小定理是 $p$ 为素数的必要不充分条件。关于 $a$ 的 Fermat 伪素数 (Fermat Pseudoprime) 指的是满足 $a^{n-1}\equiv 1(mod\ n)$ 的合数 $n$ 。例如 $2^340\equiv 1(mod\ 341)$ ，也就是说 341 是以 2 为底的伪素数。

然而， $3^340\equiv 56(mod\ 341)$ ，经过多轮 $a$ 的选择，我们似乎可以回避掉 $p$ 为伪素数的情况，但是实际上并不是。

Carmichael 数是一类特殊的伪素数：一个合数 $n$ 如果对于所有和 $n$ 互素的数 $a$ ，都满足 $a^{n-1}\equiv 1(mod\ n)$ ，那么这个数就是 Carmichael 数。可以理解为 Carmichael 数是一类特殊的伪素数，这类数能够有比较大的可能性逃过 Fermat 素性检验。最小的 Carmichael 数是 561。

# Miller-Rabin 素性检验

前面的 Fermat 素性检验对于比较大的数有一定的错误概率，因此需要有一些办法来改进素性检验。

我们可以注意到有下面情况：

二次探测定理：对于一个素数 $p$ ，整数 $x$ 满足 $x^2\equiv 1(mod\ p)$ ，那么 $x$ 可能的解只有 $1$ 和 $p-1$ 。

可以这样证明： $x^2\equiv 1(mod\ p)$ ，则有 $x^2\equiv(x+1)(x-1)\equiv 0(mod\ p)$ ，那么很明显解只能是 $x\equiv 1(mod\ p)$ 或者 $x\equiv p-1(mod\ p)$ 。

而前面的 Fermat 素性检验判定的是 $a^{p-1}\equiv 1(mod\ p)$ 。我们注意到 $p-1$ 明显应该是一个素数，因此 $a^{\frac{p-1}{2}}$ 在模 $p$ 意义下只能是 $1$ 或者 $p-1$ 。如果结果为 $1$ ，那么可以继续拆分 $\cfrac{p-1}{4},\cfrac{p-1}{8},...$ ，直到结果为一个奇数。

这也就是 Miller-Rabin 素性检验的基本思想。对于待检验的数 $p$ ，我们将 $p-1$ 分解为 $2^r\cdot t$ 的形式，其中 $t$ 为一个奇数。

接下来，我们选择一个数 $a$ ，验证 $a^{t}\mod\ p,a^{2t}\mod\ p,a^{4t}\mod\ p,...,a^{2^rt}\mod\ p$ 的值。如果这一系列数都为 1，那么 $p$ 是满足素数的条件的。如果其中出现了一个 $p-1$ ，在这之后的数都是 1，那么 $p$ 同样是满足素数的条件。但是如果一开始不为 1，后面出现了一个 1，但是在这之前的值不为 $p-1$ ，也就是不满足二次探测定理，那么 $p$ 不是素数。如果 $a^{2^rt}\mod\ p$ 不为 1，也就是不满足 Fermat 小定理， $p$ 必定不是素数。

有了上面的思想，我们可以去实现 Miller-Rabin 素性检验。

	def miller_rabin_test(p, k = 64):
	# 特判一些特殊情况
	if p == 2 or p == 3:
	return True
	if p % 2 == 0:
	return False
	# p-1=t*2^r
	t, r = p - 1, 0
	while t % 2 == 0:
	t //= 2
	r += 1
	for _ in range(k):
	# 重复 k 次判定
	a = random.randint(2, p)
	v = pow(a, t, p)
	if v == 1 or v == p - 1:
	# 后面肯定都是 1，通过
	continue
	for i in range(r):
	# 验证 2t,2^2t,... 是否满足
	v = pow(v, 2, p)
	if v == p - 1 and i != r - 1:
	# 不是在结尾的时候出现了 p-1，说明满足定理
	v = 1
	break
	if v == 1:
	# 中途直接出现了 1，不满足二次探测定理，不是素数
	return False
	# 用 Fermat 小定理进行判断
	if v != 1:
	return False
	return True

可以看出，Miller-Rabin 素性检验算法的时间复杂度为 $O(k\log{n}^3)$ ，而每一次选取随机数 $a$ 之后，如果通过了检验，那么数 $p$ 有 $1/4$ 的概率不是素数。重复 $k$ 次之后可以有 $1-4^{-k}$ 的概率确信 $p$ 是一个素数。

Miller-Rabin 算法基本上就能够确定一个数是素数，但是毕竟还是有一定的出错概率的。我们实际上可以将这个算法进行确定化。

最早 Miller 提出的素性检验算法实际上是一个确定性算法，然而这个算法依赖了目前未被证明的广义 Riemann 猜想 (GRH)，因而 Rabin 在此基础上进行了改进，提出了 Miller-Rabin 算法，也就是不依赖于 GRH 的概率性素性检验算法。

在 GRH 成立的情况下，如果 $p$ 可以通过以 $2,3,...\lfloor 2\log^2n\rfloor$ 为底数的 Miller-Rabin 素性检验，那么 $p$ 一定是素数。

这个数据量对于较大的素数 $p$ 明显并不现实，一个改进是采取前若干个素数进行检验。对于 $2^{78}$ 以内的数，采用前 12 个素数作为底数就可以验证。不过对于密码学常用的数据量来说，还是并不够用。

数论素性检验

# Fermat 素性检验

# Miller-Rabin 素性检验

椭圆曲线-SSSA Attack

数论分块