如何更好地产生大素数:筛选，然后随机采摘或随机采摘，然后检查？

Question

我正在编写RSA算法，我想知道选择初始素数(p和q)的最佳和/或通常方法是什么。

我知道有两种方法可以实现这一点，一种是基于素数筛子，另一种是基于素数测试：

1. 使用素数筛在随机范围内找到素数，然后从筛的输出中随机选取素数。
2. 随机挑选一个数字，然后测试它是否是素数。

从安全和效率的角度来看，什么是最好的方法？

Answer 1

应用密码学手册(在线) 4.62给出了Maurer生成可证明素数的算法，该算法在运行时与概率方法(通常采用Rabin-Miller检验)竞争实际感兴趣的素数大小。我最近在Python (http://s13.zetaboards.com/Crypto/topic/7234475/1/)中实现了Maurer的算法。