RSA 公钥密码学首先找到几个大素数。本质上，你是通过测试随机数直到找到素数来做到这一点的，但并不完全是这样。
Filippo Valsorda 刚刚发表了一篇关于此的好文章。
假设您正在寻找 1024 位素数。您生成随机 1024 位数字，然后进行测试，直到找到一个质数。通过将最后一位设置为 1，您可以立即使此过程加快两倍：每次碰巧抽到偶数时都生成一个新数字是浪费的。
不太明显的是，设置顶部位也是很常见的。当您生成 0 到 2 1024 − 1 之间的数字时，您可能会生成一个较小的数字。您可能会生成一个非常小的数字，例如 59，但可能性极小。但是，例如，您不太可能生成 2 1020左右的数字。通过设置最高位，您知道您正在生成 2 1023和 2 1024之间的数字。
大多数合数都有较小的因数，因此在运行更耗时的测试之前，您需要检查是否能被 3、5、7 等整除。概率测试比确定性测试更有效，因此实际上每个人都在 RSA 中使用可能的素数。有关如何应用这些测试以及要运行多少测试的详细信息，请参阅 Filippo Valsorda 的文章。
您是否应该担心确定主要候选人的最高位？有一些天真的和复杂的理由不让工作担心，还有一个至少考虑一下的中间理由。
天真的反应是你只是失去了一点随机性。这会造成多大伤害？但在其他情况下，例如丢失 AES 密钥中的一位随机性，人们确实担心这种损失。
RSA 模数的质因数中的位并不直接对应于安全位。 2048 位模数是两个 1024 位素数的乘积，其安全性约为 112 位。 （请参阅NIST SP 800-57 。）您可以在失去一点安全性之前在质因数中设置几个位。如果这让您感到困扰，请升级为使用 3072 位模数，而不必担心 2048 位模数在某种意义上是 2046 位模数。
更多密码学帖子
为密码学生成素数的详细信息帖子首次出现在John D. Cook上。
原文： https://www.johndcook.com/blog/2024/12/31/generating-primes-for-rsa/