我知道我可以在互联网上找到许多文章来解释RSA算法的原理可以对消息进行加密和解密，但是我似乎找不到任何文章来说明用于生成
p和q算法的算法，该算法使用的是大而不同的素数。#1 楼
生成大质数的标准方法是采用所需长度的预选随机数，进行Fermat测试（最好使用基数$ 2 $，因为可以针对速度进行优化），然后应用一定数量的Miller-Rabin测试（取决于长度和所允许的错误率，例如$ 2 ^ {-100} $）来得到一个很可能是质数的数字。预选可以通过将测试除以小数来完成质数（最多几百个）或通过筛选最多10,000-1,000,000的质数，考虑许多形式为$ b + 2i $（$ b $ big，$ i $多达几千）的素数候选项。
据我所知，AKS的确定性质数测试尚未使用，因为它速度较慢，并且有可能由硬件引起的计算错误高于$ 2 ^ {-100} $。
大多数智能卡都提供模数从1024到几千位的模数协处理器。制造商通常还提供使用协处理器生成RSA和RSA密钥的库。
#2 楼
FIPS 186-3告诉您他们如何期望您为加密应用程序生成素数。本质上是米勒-拉宾（Miller-Rabin），但是它还指定了需要素数的额外属性时该怎么做。
评论
$ \ begingroup $
+1提到了FIPS，这与大多数实现所使用的不同。
$ \ endgroup $
–萨摩斯
2011年7月13日在13:26
$ \ begingroup $
FIPS 186-3附录C，F
$ \ endgroup $
–ir01
2011年7月13日在17:07
$ \ begingroup $
新版（2013年7月）是FIPS 186-4。
$ \ endgroup $
– Der Kommissar
2015年6月7日13:29在
#3 楼
由于质数很常见：π（n）〜n / ln（n），因此生成质数的问题简化为确定素数（而不是专门设计用于生成质数的算法）之一。概率使用测试（例如
java.math.BigInteger.probablePrime()中）而不是确定性测试。请参阅Miller-Rabin。http://en.literateprograms.org/Miller-Rabin_primality_test_%28Java%29
关于RSA的质数，还有一些其他较小的要求，即（p-1）和（q-1）不应轻易分解，并且p和q不应靠近。
评论
$ \ begingroup $
次要校正：要求不是p-1（和q-1）不应该容易分解。它们可以是素数的两倍（因此容易分解），不会出现问题。他们不应该做到的很顺利；也就是说，仅由小的（可能的）因素组成。
$ \ endgroup $
–雨披
2011年8月27日，1：14
$ \ begingroup $
而且，“附加的次要要求”由随机生成的素数自动满足（命中“坏素数”的风险要比疯狂的浣熊将PC咬死的风险要低得多）。同样，ECM因式分解方法可以看作是Pollard的$ p-1 $方法的扩展，您无法用这种测试来辩护，因此您已经依赖于浣熊大小的低风险。
$ \ endgroup $
–托马斯·波宁（Thomas Pornin）
11年8月30日在12:38
#4 楼
有一些测试可确定给定数是否为质数，例如Miller–Rabin素数测试。这些算法确定给定数是否为概率为P的素数。#5 楼
如其他答案所示，不是使用概率方法生成大素数，而是可以（更好的IMHO）采用Maurer算法生成可证明素数。我有一个实现该算法的Python代码，可在s13.zetaboards.com/Crypto/topic/7234475/1/获得
#6 楼
您可以做的是使用密尔常数生成。然后，无论如何，对素数的测试都是好的...（如果选择的常数不够精确，那么您可能会得到非素数）米尔的常数就是这样一个数字，如果乘以3，然后乘以任意N，其中N是一个无符号整数，我们得到的值V wich（向下取整）是一个质数。
因此，令C为常数
C = 1.3063778838630806904686144926 ....
然后让
L = C^3
然后从<0，infinite>中选择任意N，N为整数
<
prime = round down( L^N )
它有几个缺点，例如常数必须非常精确，如果常数不够精确，则最终将得到合成数。但是，事实证明，“算法”总是生成质数。
我听说的下一个缺点是，随着指数的增加，将需要更多的计算能力。但是， do会生成其中的两个，所以它可以做...
为进一步阅读，以下是我发现作为参考。
https://en.wikipedia.org/wiki/ Mills％27_constant
评论
$ \ begingroup $
我不知道这是为RSA生成素数的行业标准方法。一方面，它并不是一种真正的算法（也就是说，除非您为Mill的常数提供精确准确的值，否则它不是），此外，它也不擅长生成（例如）1024位素数（充其量就可以） ，仅产生一个相同大小的素数）。
$ \ endgroup $
–雨披
16年6月18日在18:55
评论
$ \ begingroup $
哇，概率算法的失败率比确定性算法的失败率低-因为我们处于由硬件来计算错误的规模上。我说对了吗？
$ \ endgroup $
– Atte Juvonen
16 Jul 29'0:05
$ \ begingroup $
很难说，这是何时发生的。由于概率算法的运行速度快于确定性算法，因此它不太可能受到宇宙射线的干扰。
$ \ endgroup $
– j.p.
16年7月29日在8:21
$ \ begingroup $
@ j.p .：我在Python Maurer的算法中与Miller-Rabin的算法进行了比较，发现它们在实际应用中相当可比。参见s13.zetaboards.com/Crypto/topic/7234475/1/
$ \ endgroup $
–沉莫功
16年7月29日在10:45
$ \ begingroup $
@ Mok-KongShen：“首先通过一组适当的小素数对试验进行除法测试，然后通过Miller-Rabin测试对t的不同值进行素数测试，但这并不是查找素数的快速方法。在进行Miller-Rabin试验之前，使用筛子和一个Fermat试验（至基数2）来筛查筛子中的残留物，其速度至少应快一倍。
$ \ endgroup $
– j.p.
16年7月30日在15:53
$ \ begingroup $
@ j.p。比AKS更好的算法可能是ECPP，因为它可以生成素数证书，该素数证书可用于快速验证整数是否为素数，从而消除了硬件错误的风险。
$ \ endgroup $
–森林
18/12/8在5:30