产生真正的素数

Question

我正在玩耍，并试图编写RSA的实现。问题在于，我坚持生成生成钥匙对涉及的大量质数。有人可以将我指出一种快速产生巨大的素数/可能的素数的方法吗？

Answer 1

您不会确切生成质数。您会随机生成一个较大的奇数，然后测试该数字是否为素数，如果未随机生成另一个数字。有一些质数定律基本上表明您通过随机尝试“击中”素数的几率是（2/ln n）

例如，如果您想要一个512位随机数字，您会发现2/（512*ln（2））中的一个，因此您尝试的数字中每177个中大约有1个是素数。

有多种测试数字是否是素数的方法，一个好的是“米勒 - 拉宾测试” 如这个问题的另一个答案所述.

此外，OpenSSL还可以测试素数：

$ openssl prime 119054759245460753
1A6F7AC39A53511 is not prime

Answer 2

看看如何 TrueCrypt 可以。另外，看看 Rabin-Miller 用于测试大型伪气。

Answer 3

您没有提及您正在使用的语言。有些有一种内置的方法。例如，在Java中，这就像调用一样容易 NextProbablePrime（） 在一个biginteger上。

Answer 4

上一个答案不正确：2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 = 509 * 59。

我认为海报正在误解（真实的）证据，证明存在数量不可数的数字。

Answer 5

Mono有一个像Java一样开源的Biginteger课程。您可以看看那些。它们可能是便携式的:) g'luck

Answer 6

由于U. Maurer引起的算法，它会产生随机证明的（与统计上高度可概括的）素数，几乎均匀地分布在特殊尺寸的所有素数上。我有一个相当有效的python实施：http://s13.zetaboards.com/crypto/topic/7234475/1/