我正在玩耍并尝试编写 RSA 的实现。问题是我一直在生成大量质数，这些质数涉及生成密钥对。有人能指出一种快速生成巨大素数/可能素数的方法吗？
问问题
5915 次
5 回答
19
您不会准确生成素数。您随机生成一个大的奇数，然后测试该数字是否为素数，如果不是随机生成另一个。有一些素数定律基本上表明你通过随机尝试“命中”素数的几率是 (2/ln n)
例如，如果你想要一个 512 位的随机素数，你会在 2/(512*ln(2)) 中找到一个，所以你尝试的每 177 个数字中大约有 1 个是素数。
有多种方法可以测试一个数字是否为素数，一个好的方法是“Miller-Rabin 测试” ，如该问题的另一个答案中所述。
此外，OpenSSL 有一个很好的工具来测试素数：
$ openssl prime 119054759245460753
1A6F7AC39A53511 is not prime
于 2009-07-20T23:57:27.160 回答
3
看看TrueCrypt是如何做到的。此外，请查看Rabin-Miller以测试大型伪素数。
于 2009-07-18T00:31:12.170 回答
3
U. Maurer 有一种算法可以生成随机可证明的（与统计上高度可能的）素数，这些素数几乎均匀分布在特殊大小的所有素数的集合上。我有一个相当有效的 Python 实现：http: //s13.zetaboards.com/Crypto/topic/7234475/1/
于 2015-01-20T11:36:05.413 回答
2
你没有提到你使用的是什么语言。有些内置了执行此操作的方法。例如，在 java 中，这就像在 BigInteger 上调用nextProbablePrime()一样简单。
于 2009-07-18T00:32:19.427 回答
1
Mono 有一个 BigInteger 类，它和 java 一样是开源的。你可以看看那些。它们可能是便携式的:) g'luck
于 2009-07-20T07:34:16.463 回答