素性检验

素性检验判断给定整数 $n$ 是否为素数。它比分解容易得多：现代算法在 $n$ 的位数多项式时间内完成判定，而大数分解没有已知的经典多项式算法——这一"易检验、难分解"的不对称性是 RSA 等公钥密码的安全基础。

试除法

用不超过 $\sqrt n$ 的素数逐个试除，正确但随 $n$ 指数变慢，只适合小整数，也常作为其他算法的预处理。

费马检验与伪素数

由费马小定理：若 $n$ 为素数且 $\gcd(a,n)=1$，则 $a^{n-1}\equiv1\pmod n$。取若干基 $a$ 验证之。但存在伪素数（如 $341=11\cdot31$）使 $2^{340}\equiv1\pmod{341}$，费马检验会误判。

Miller–Rabin 检验

写 $n-1=2^s d$（$d$ 为奇数）。若 $n$ 为素数，则 $a^d\equiv1\pmod n$ 或存在 $0\le r<s$ 使 $a^{2^r d}\equiv-1\pmod n$。依次检验 $a^d,a^{2d},\dots$：若全不满足则 $n$ 为合数。

• 随机取 $k$ 个基：单次误判概率不超过 $4^{-k}$，实际取 $k\approx20$ 即可
• 确定性版本：$n<2^{64}$ 时取基 $\{2,325,9375,28178,450775,9780504,1795265022\}$ 可精确判定

AKS 检验

2002 年 Agrawal–Kayal–Saxena 给出确定性多项式时间算法（$O((\log n)^{6+\varepsilon})$），从理论上证明素性检验属多项式时间可解，但常数过大，实践中以 Miller–Rabin 为主。

示例

$n=341=11\cdot31$，$n-1=340=85\cdot2^2$，取基 $a=2$：

• $2^{10}=1024\equiv1\pmod{341}$，故 $a^d=2^{85}\equiv2^5=32$
• $a^{2d}=32^2\equiv1$，既非 $1$ 也非 $-1$，两个条件都不满足 → $341$ 为合数
  同一 $n$ 满足 $2^{340}\equiv1\pmod{341}$，费马检验误判为素数，而 Miller–Rabin 正确识别。

应用

素性检验是大素数生成与 RSA 密钥选择的必要步骤，也是大数分解算法（先判是否合数）的前置环节。