Miller-Rabin 测试告诉了我们什么？

基本流程

• 在 $(1, n-1) \cap \mathbb{N}$ 中随机选择一个数 $a$（假定 $n$ 较大，不考虑边界情况）；
• 将 $n$ 写成 $s \cdot 2^t$ 的形式，其中 $2 \nmid s$，$t\in\mathbb{N}$；
• 计算 $a_0 = a^{s} \bmod n$，若 $a_0 = 1$，返回 $\mathtt{false}$；
• 依次计算序列 $\langle a_0, a_1, a_2, \ldots, a_t \rangle$，其中 $a_i = 2 \cdot a_{i-1} \bmod n$（$i \geqslant 1$）；
• 若 $a_t \neq 1$，返回 $\mathtt{true}$；
• 若存在 $i \geqslant 1$ 使得 $a_i = 1$ 且 $a_{i-1} \notin \{-1, 1\}$，返回 $\mathtt{true}$；
• 返回 $\mathtt{false}$．

思想和错误率

1. 费马小定理
   $$a^{p-1} \equiv 1 \pmod{p}$$
2. 二次探测定理
   在模 $p$ 意义下，满足 $a^2 \equiv 1 \pmod{p}$ 的 $a$ 只有 $\pm 1$．

并且可以证明¹，当 $n$ 是合数时，强骗子的数量至多为 $\frac{\varphi(n)}{4}$，且存在 $n$ 使得该上界达到．

贝叶斯概率分析