Prime Number
素数是大于 1 且仅能被 1 和自身整除的自然数，是数论的积木，所有整数可唯一分解为素数积。
用途
作为整数的积木，是数论与密码学（RSA）的基础。
机制
大于 1 的自然数，约数仅有 1 与自身。算术基本定理：每个整数可唯一分解为素数积。素性测试：试除、Miller-Rabin（概率）、AKS（确定但慢）。素数无限（欧几里得证明）。
用例
- RSA 密钥生成
- Diffie-Hellman 参数
- 哈希表素数容量
- 数论研究
示例
- 输入
The first 10 primes输出2,3,5,7,11,13,17,19,23,292 is the only even prime
常见错误
- Using small primes for RSA moduli
- Use large primes (≥1024 bits)