生成非常大的素数
我正在尝试编写 RSA 的实现。 问题是我一直在生成生成密钥对所涉及的大量素数。 有人能指出一种快速生成巨大素数/可能素数的方法吗？
I'm playing around and trying to write an implementation of RSA. The problem is that I'm stuck on generating the massive prime numbers that are involved in generating a key pair. Could someone point me to a fast way to generate huge primes/probable primes?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
你不能准确地生成素数。 您随机生成一个大奇数，然后测试该数字是否为素数，如果不是则随机生成另一个。 有一些素数定律，基本上规定通过随机尝试“击中”素数的几率是 (2/ln n)
例如，如果您想要一个 512 位随机素数，您会发现 2/ 之一(512*ln(2))
因此，您尝试的每 177 个数字中，大约有 1 个是素数。
有多种方法可以测试一个数字是否为素数，一个好的方法是“米勒-拉宾测试”如另一个答案中所述问题。
此外，OpenSSL 有一个很好的实用程序来测试素数：
You don't generate prime numbers exactly. You generate a large odd number randomly, then test if that number is prime, if not generate another one randomly. There are some laws of prime numbers that basically state that your odds of "hitting" a prime via random tries is (2/ln n)
For example, if you want a 512-bit random prime number, you will find one in 2/(512*ln(2))
So roughly 1 out of every 177 of the numbers you try will be prime.
There are multiple ways to test if a number is prime, one good one is the "Miller-Rabin test" as stated in another answer to this question.
Also, OpenSSL has a nice utility to test for primes:
看看 TrueCrypt 是如何做到的。 另外，请查看 Rabin-Miller 用于测试大型伪素数。
Take a look at how TrueCrypt does it. Also, take a look at Rabin-Miller for testing large pseudoprimes.
U. Maurer 提出了一种算法，可以生成随机的可证明（与统计上高度可能的）素数，这些素数几乎均匀分布在所有特殊大小的素数集合上。 我有一个它的 Python 实现，它在以下方面相当有效：
http://s13.zetaboards.com/Crypto/topic/7234475/1/
There is an algorithm due to U. Maurer that generates random provable (in contrast to statistically highly-probable) primes that are almost uniformly distributed over the set of all primes of a special size. I have a Python implementation of it that is fairly efficient at:
http://s13.zetaboards.com/Crypto/topic/7234475/1/
你没有提到你使用什么语言。 有些内置了执行此操作的方法。例如，在 java 中，这就像调用 nextProbablePrime()。
You didn't mention what language you are using. Some have a method of doing this built in. For example, in java this is as easy as calling nextProbablePrime() on a BigInteger.
Mono 有一个 BigInteger 类，它和 java 一样都是开源的。 你可以看看那些。 它们可能是便携式的:)祝你好运
Mono has a BigInteger class that's open source as does java. You could take a look at those. They're probably portable :) g'luck