概述
费马小定理：$a^{p - 1} \equiv 1 \pmod p$ 当 $p$ 是质数且 $a$ 是小于 $p$ 的正整数。
但是费马小定理的逆定理不成立，比如 $2^{340} \equiv 1 \pmod{341}$，但是 $341 = 11 \times 13$。
Miller 和 Rabin 提出了二次探测定理：
假设有 $x^2 \equiv 1 \pmod p$，那么 $x = 1$ 或 $x = p - 1$。
证明：
$$ \begin{aligned} x^2 - 1 &\equiv 0 \pmod p \\ (x + 1)(x - 1) &\equiv 0 \pmod p \end{aligned} $$
所以 $x = 1$ 或 $x = p - 1$。
当 $x = 1$ 或 $x = p - 1$ 时，$x$ 都有可能是质数。
举个例子：
现在取 $p = 2$，检验 $341$ 是否是质数：
$2^{340} = \left(2^{170}\right)^2$，把上面的定理套进去，并计算 $2^{170} \mod 341$ 的值，发现是 $1$，满足要求，于是继续套用公式，计算 $2^{85} \mod 341$，发现其等于 $32$。这时我们就可以确定 $341$ 是一个合数。
所以我们的计算过程就是不断地令指数除以 $p$，然后对模数取模进行判断。
当出现取模之后的结果不为 1 或 $p - 1$ 时，证明它不是质数。如果指数已经是奇数了，那么它就是一个质数。
但有时可以不这么做，只看第一次检测，如果通过就换下一个 $p$ 进行测试。
单独使用某个 $p$ 进行判断可能会检测不出来，例如 $2047$ 就能通 $p = 2$ 时的测试。取多个不同的 $p$ 可以降低检测错误的概率。
hzt · 2022-10-11 14:56
%%%%%%%%%%%%%%%%%%%%%%%%