如何在java中生成160位素数？

问题描述

我想在java中生成一个160位的素数。我知道我必须循环遍历所有160位数字和任何数字 n ，我必须检查它们是否可以被任何小于 sqroot（n）或任何素性测试，如 Miller-Rabin测试。我的问题是：

I want to generate a 160-bit prime number in java. I know that I'll have to loop through all the 160-bit numbers and for any number n, I'll have to check if they are divisible by any primes less than sqroot(n) or by any primality test like Miller-Rabin test. My questions are:

1. 是否有任何特定的库可以做到这一点？

1. Is there any specific library which does this?

还有其他（更好）的方法吗？

Is there any other (better) way to do this?

推荐答案

生成 BigInteger 几乎肯定是素数 - 它不素数的概率小于你被闪电击中的概率。一般来说， BigInteger 已经经过严格测试和优化内置的素性测试操作。

BigInteger.probablePrime(160, new Random()) generates a BigInteger that is almost certainly prime -- the probability that it is not a prime is less than the probability that you will get struck by lightning. In general, BigInteger already has heavily tested and optimized primality testing operations built in.

对于它的价值，这不会永远是因为素数定理，随机选择的n位数的概率与素数的1 / n成正比，所以平均来说你只需要尝试O（n）个不同的随机n位数字之前你会找到一个最好的数字。

For what it's worth, the reason this won't take forever is that by the prime number theorem, a randomly chosen n-bit number has probability proportional to 1/n of being prime, so on average you only need to try O(n) different random n-bit numbers before you'll find one that's prime.

这篇关于如何在java中生成160位素数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！