1. 引言
在之前的一篇文章中我们探讨了密码学算法的基本原理与计算复杂度。许多密码算法依赖于大素数的生成与处理，因此对素数的可靠性验证变得至关重要。
最直观的素数验证方法是试除法，也就是尝试将 n 依次除以大于等于 2 的整数。然而这种方法所需的时间是指数级的，而非多项式时间。
在本文中，我们将介绍一种不依赖因式分解的素性测试方法：Miller-Rabin 方法。我们会从一个更简单的伪素数测试出发，逐步过渡到 Miller-Rabin 方法，从而降低误判的概率。
2. 伪素性测试
模 n 的同余是一种同余关系（congruence relation），它兼容加法、减法和乘法运算。我们通常写作：
$$ a \equiv b \pmod{n} $$
括号中的 mod n 表示该同余关系适用于整个等式，而不仅仅是右边的 b。
如果 n 是合数且满足：
$$ a^{n-1} \equiv 1 \pmod{n} $$
则称 n 是以 a 为底的伪素数。
由此我们可以得出几个重要结论：
- ✅ 如果
n是素数，则对于任意非零的a，n都是a的伪素数。 - ✅ 如果能找到一个
a使得n不满足伪素数定义，则n必然是合数。 - ✅ 更有意思的是，反过来也“几乎”成立，也就是说我们可以通过检查伪素数条件来判断一个数是否为素数。
具体来说，我们只需验证 a = 2 时的伪素数条件。如果条件不满足，则 n 肯定是合数；否则，我们“希望” n 是素数。更准确地说，此时 n 要么是素数，要么是以 2 为底的伪素数。
下面的伪代码实现了基于上述逻辑的素性测试（适用于 n > 2）：
algorithm Pseudoprime(n):
// INPUT
// n = 待测试的整数
// OUTPUT
// COMPOSITE：如果 n 明确是合数
// PRIME：如果 n 可能是素数
if 2^(n-1) mod n != 1:
return COMPOSITE
else:
return PRIME
PSEUDOPRIME 函数会在 n 是素数但同时也是以 2 为底的伪素数时出错。当 n 是合数时，该函数总是能正确判断。接下来我们将介绍如何减少这种误判的概率。
（未完待续）