素性测试

素性测试是判断一个自然数是否为素数的测试。素数是只能被 1 和自身整除且大于 1 的自然数（2, 3, 5, 7, 11, 13...）。RSA 加密算法就用到了大素数，因此素性测试在密码学中非常重要。

逐个除以 2 到 √n 之间的数，看能否整除：

判断 3599 是否为素数:
  √3599 ≈ 59.99，只需除以 2~59

  3599 mod 2 = 1
  3599 mod 3 = 2
  ...
  3599 mod 59 = 0  → 能被 59 整除，不是素数

这种方法对于大数非常慢。

如果 p 是素数，对于任意小于 p 的正整数 n：

n^p mod p = n

例如，素数 5：

1^5 = 1     mod 5 = 1  ✓
2^5 = 32    mod 5 = 2  ✓
3^5 = 243   mod 5 = 3  ✓
4^5 = 1024  mod 5 = 4  ✓

根据费马小定理判断素数——随机选几个数测试是否满足 n^p mod p = n：

判断 113 是否为素数:
  64^113 mod 113 = 64  ✓
  29^113 mod 113 = 29  ✓
  15^113 mod 113 = 15  ✓

  3 次都满足 → 很可能是素数

测试次数越多，是素数的概率越大。但极少数合数（卡迈克尔数，如 561 = 3×11×17）也能通过所有测试。

费马测试的改进版，是 RSA 算法中实际使用的素性测试方法。重复测试后，当不是素数的概率小于 0.5⁸⁰ 时，就可以判定为素数。

#素性测试