encryption - 产生非常大的素数

Question

我正在玩耍并尝试编写 RSA 的实现。问题是我一直在生成大量质数，这些质数涉及生成密钥对。有人能指出一种快速生成巨大素数/可能素数的方法吗？

score 19 · Accepted Answer

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

例如，如果你想要一个 512 位的随机素数，你会在 2/(512*ln(2)) 中找到一个，所以你尝试的每 177 个数字中大约有 1 个是素数。

有多种方法可以测试一个数字是否为素数，一个好的方法是“Miller-Rabin 测试” ，如该问题的另一个答案中所述。

此外，OpenSSL 有一个很好的工具来测试素数：

$ openssl prime 119054759245460753
1A6F7AC39A53511 is not prime

score 3 · Accepted Answer

3

看看TrueCrypt是如何做到的。此外，请查看Rabin-Miller以测试大型伪素数。

于 2009-07-18T00:31:12.170 回答

score 3 · Accepted Answer

U. Maurer 有一种算法可以生成随机可证明的（与统计上高度可能的）素数，这些素数几乎均匀分布在特殊大小的所有素数的集合上。我有一个相当有效的 Python 实现：http: //s13.zetaboards.com/Crypto/topic/7234475/1/

score 2 · Accepted Answer

你没有提到你使用的是什么语言。有些内置了执行此操作的方法。例如，在 java 中，这就像在 BigInteger 上调用nextProbablePrime()一样简单。

score 1 · Accepted Answer

Mono 有一个 BigInteger 类，它和 java 一样是开源的。你可以看看那些。它们可能是便携式的:) g'luck

5 回答 5