但是假设我这样做：
选择随机的奇数1024位数字$ n $
如果$ n $是质数，则返回$ n $
$ n \ leftarrow n + 2 $
转到2
（这种方法可以通过筛分更快地选择质数。）
由于质数未均匀地分布在数字线上，因此该算法似乎更喜欢长后缀的质数复合材料的运行。在$ 2 ^ {1024} $周围用数字表示，以x表示质数：
--- xx -------------- -------------- x ------------------------ x --- x
很明显，我们上面的算法找到上面的第三个素数的可能性比找到第二个素数的可能性大。
问题：这是一个问题吗？
#1 楼
此过程称为“增量搜索”，在“应用密码学手册”（第148页注释4.51）中对此进行了描述。尽管选择了一些素数比其他素数具有更高的概率，但是这不允许对RSA进行已知攻击。粗略地说，增量搜索会选择本来可以选择的素数，但仍然有数以百万计的素数。 OpenSSL使用这种主要生成技术。#2 楼
不，不认为这是一个问题，可能是因为：没有已知的因子分解方法可以利用偏见
偏见实际上并没有那么大至少，当您将其与质数进行比较时。给定素数的密度在$ 2 ^ {1024} $左右，则在连续$ 2000 $的奇数合成之后可能会立即出现素数。这样的素数将有大约$ 2000/2 ^ {1022} \ approx 2 ^ {-1011} $的概率被选择。在另一个极端上，紧接另一个素数（双素数）的素数有被选择$ 2 ^ {-1022} $的概率。 $ 2 ^ {-1011} $和$ 2 ^ {-1022} $之间似乎并没有太大的区别。
此外，用于查找素数的现有标准（X9.31，X9 .80）认可上述类型的线性搜索（即使它们在某些细节上有所不同，例如，增量不是2，而是其他偶数）。
评论
$ \ begingroup $
您在最后一段中提到的“详细信息”很重要-请参阅fgrieu对OP的评论。
$ \ endgroup $
– TonyK
19年5月27日14:57
$ \ begingroup $
@TonyK：实际上，我不确定这是否重要？较大的步长不会产生一致性（但是，相同的推理也暗示了这一点-我们仍然不知道如何利用它）。实际上，如果您故意选择素数$ m $使得$ m-1 $的素数为固定大小，那么您将永远不会生成$ m-1 $没有素数的素数，因此可以说与均匀性的偏差更大
$ \ endgroup $
–雨披
19年5月27日在22:04
$ \ begingroup $
最近有人这样做吗？我的意思是选择素数$ n $使得$ n-1 $具有很大的素数因子。 （顺便说一句，如果随机选择步长，则较大的步长确实会提高均匀性。）
$ \ endgroup $
– TonyK
19年5月28日在7:07
$ \ begingroup $
@TonyK：我相信FIPS仍然坚持这样做，因此我怀疑有很多实现（尽管出于与统一性无关的原因）
$ \ endgroup $
–雨披
19年5月28日在12:06
$ \ begingroup $
这似乎是有关该主题的最新FIPS出版物。它允许使用可证明的素数（在这种情况下您是对的）和可能的素数（在这种情况下，$ n-1 $的因子不附加任何条件）。
$ \ endgroup $
– TonyK
19年5月28日在13:53
评论
问题是，对于某个偶数m，可以通过用n <-n + m替换n <-n + 2来规避问题，这是在过程开始时随机绘制的。这仍然允许通过筛分快速选择质数。对于某个随机素数p，有时用m = 2 * p完成，并允许仅枚举那些n，以使p除以n-1。