素数与唯一分解

只能被 $1$ 和自身整除的整数 $>1$ 是素数。算术基本定理：每个整数唯一地分解为素数之积——素数是乘法的「原子」。素数有无穷多个（欧几里得反证），其分布由素数定理刻画：不超过 $x$ 的素数约 $x/\ln x$ 个。

素性检验

RSA 需要随机生成大素数（数百位），不能靠试除。用概率素性测试：

  • 费马测试：若 $a^{n-1}\not\equiv1\pmod n$ 则 $n$ 必合数（但有 Carmichael 数骗过它）；
  • Miller–Rabin：改进版，多轮随机基，将「误判为素」的概率压到任意小，是工程标准。

例题

例　$561=3\times11\times17$ 是合数，却对所有与它互素的 $a$ 满足 $a^{560}\equiv1$（Carmichael 数），费马测试会被骗，Miller–Rabin 则能识破。

应用

RSA / DH 密钥生成的第一步就是「随机取大素数」，靠 Miller–Rabin 高效产出；素数稀疏但足够多（素数定理保证随机抽样能很快撞到），使生成 2048 位素数在毫秒级可行。