素性测试与工业级素数生成
内容提要
RSA 密钥生成的关键步骤是找到两个大素数 p 和 q。由于大数素性测试复杂，工业界采用概率算法，如 Miller-Rabin 测试。文章介绍了多种素性测试方法，包括 Fermat 小定理、Miller-Rabin 测试和 Baillie-PSW 测试，并探讨了 OpenSSL 生成素数的过程及注意事项。强调了选择合适的素性测试方法和参数在实际应用中的重要性。
关键要点
-
RSA 密钥生成的第一步是找到两个大素数 p 和 q。
-
试除法是最直观的素性测试方法，但对于大数不可行，时间复杂度为 O(sqrt(n))。
-
Fermat 小定理提供了一种素性测试方法，但存在 Carmichael 数的缺陷。
-
Miller-Rabin 测试通过引入二次探测来增强 Fermat 测试的可靠性，错误概率为 4^(-k)。
-
Baillie-PSW 测试结合了 Miller-Rabin 和 Lucas 测试，至今没有已知反例。
-
AKS 算法是第一个确定性的多项式时间素性测试，但在实际应用中效率较低。
-
Lucas-Lehmer 测试专用于 Mersenne 素数，效率高于通用素性测试。
-
工业级素数生成通常采用随机候选数生成、小素数试除和多轮 Miller-Rabin 测试的流水线。
-
OpenSSL 的 BN_check_prime 函数实现了多种素性测试方法，确保生成的素数安全。
-
在 RSA 密钥生成中，选择合适的素数 p 和 q 及其差值的安全性至关重要。
延伸问答
RSA 密钥生成中如何选择大素数 p 和 q？
在 RSA 密钥生成中，选择的素数 p 和 q 需要满足安全性要求，如 |p - q| 应足够大，以防止 Fermat 因式分解。
Miller-Rabin 测试的错误概率是多少？
Miller-Rabin 测试的错误概率为 4^(-k)，其中 k 是测试轮数。
Baillie-PSW 测试的特点是什么？
Baillie-PSW 测试结合了 Miller-Rabin 测试和 Lucas 测试，至今没有已知的反例，提供了高可靠性。
AKS 算法的复杂度如何？
AKS 算法的复杂度为 O((log n)^6)，尽管是多项式时间，但在实际应用中效率较低。
OpenSSL 如何实现素性测试？
OpenSSL 的 BN_check_prime 函数实现了多种素性测试方法，包括小素数试除和 Miller-Rabin 测试。
Fermat 小定理的缺陷是什么？
Fermat 小定理的缺陷在于存在 Carmichael 数，这些合数可以欺骗 Fermat 测试，使其误判为素数。
