logo标签列表

生成超大的质数

encryptionrsaprimespublic-key
11

我正在尝试编写 RSA 算法的实现，但卡在了生成大质数这一步骤上。 请问有什么快速生成大素数或可能为质数的方法吗？

5个回答
20
你并不会精确地生成质数。你会随机生成一个大的奇数，然后测试这个数字是否是质数，如果不是就再随机生成一个。质数有一些规律，基本上表明通过随机尝试获得质数的几率为(2/ln n)。
例如，如果你想要一个512位的随机质数，你将在2/(512*ln(2))中找到一个。所以你大约需要尝试177次才能找到一个质数。
有多种方法可以测试一个数字是否为质数，其中一个好的方法是“Miller-Rabin测试”，正如这个问题的另一个回答中所述。
此外，OpenSSL还有一个很好的实用程序来测试质数：
$ openssl prime 119054759245460753
1A6F7AC39A53511 is not prime
1
谢谢。这解释了我遇到的很多问题。 - nonpolynomial237
1
您也可以在 OpenSSL 中生成质数：openssl prime -generate -bits 512。 - mykhal
最大的512位质数是2**512-569，使用以下命令找到：python -c 'print("\n".join([str(2**512-(x*2+1)) for x in range(1000)]))' | xargs -n 1 openssl prime。 - Erik Aronesty
3
为什么你认为TrueCrypt会生成质数？据我所知，它只使用对称加密。 - CodesInChaos
3

有一种算法是由U. Maurer提出的，它可以生成随机且可以被证明为质数（与统计上高概率不同），这些质数几乎均匀地分布在特定大小的所有质数集合中。我有一个Python实现它，效率相当高，网址如下： http://s13.zetaboards.com/Crypto/topic/7234475/1/

2
您没有提到您使用的语言。有些语言内置了这种方法。例如，在Java中，只需在BigInteger上调用nextProbablePrime()即可轻松完成此操作。
根据该功能的实现方式，如果搜索空间被减少，您可能会危及到密钥选择。 - Stephen
1

在Mono和Java中都有开源的BigInteger类，您可以查看一下。它们可能是可移植的:) 祝好运

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接