encryption - 生成非常大的素数

Question

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

Answer 1

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

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

有多种方法可以测试一个数是否为质数，一种很好的方法是“Miller-Rabin 测试”as stated in another answer to this question .

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

$ openssl prime 119054759245460753
1A6F7AC39A53511 is not prime