java 用Java生成精确的素数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2882147/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Generating exactly prime number with Java
提问by Viet
I'm aware of the function BigInteger.probablePrime(int bitLength, Random rnd) that outputs probably prime number of any bit length. I want a REAL prime number in Java. Is there any FOSS library to do so with acceptable performance? Thanks in advance!
我知道函数 BigInteger.probablePrime(int bitLength, Random rnd) 可能输出任何位长的素数。我想要一个真正的 Java 素数。是否有任何 FOSS 库可以以可接受的性能做到这一点？提前致谢！
EDIT:
编辑：
I'm looking at 1024 & 2048 bit primes.
我在看 1024 和 2048 位素数。
回答by Jason S
- use probable prime to generate a candidate
- use a fast deterministic testsuch as the AKS primality testto check whether the candidate is indeed prime.
edit:Or, if you don't trust the isProbablePrime to be large enough certainty, use the BigInteger constructor BigInteger(int bitLength, int certainty, Random rnd)that lets you tune your certainty threshold:
编辑：或者，如果您不相信 isProbablePrime 的确定性足够大，请使用 BigInteger 构造函数BigInteger(int bitLength, int certainty, Random rnd)来调整确定性阈值：
certainty - a measure of the uncertainty that the caller is willing to tolerate. The probability that the new BigInteger represents a prime number will exceed (1 - 1/2certainty). The execution time of this constructor is proportional to the value of this parameter.
确定性 - 调用者愿意容忍的不确定性的度量。新 BigInteger 表示素数的概率将超过 (1 - 1/2确定性)。此构造函数的执行时间与此参数的值成正比。
Probabilistic tests used for cryptographic purposes are guaranteed to bound the probability of false positives -- it's not like there's some gotcha numbers that exist that will sneak through, it's just a matter of how low you want the probability to be. If you don't trust the Java BigInteger class to use these (it would be nice if they documented what test was used), use the Rabin-Millertest.
用于加密目的的概率测试保证会限制误报的概率——并不是说存在一些会偷偷通过的陷阱数字，这只是你希望概率有多低的问题。如果您不相信 Java BigInteger 类会使用这些（如果他们记录使用的测试会很好），请使用Rabin-Miller测试。
回答by Michael Borgwardt
There are some methods to generate very large primes with acceptable performance, but not with sufficient density for most purposes other than getting into the Guiness Book of Records.
有一些方法可以生成具有可接受性能的非常大的素数，但除了进入吉尼斯世界纪录之外，对于大多数目的来说，密度不够。
Look at it like this: the likelihood that a number returned by probablePrime()is not prime is lower than the likelihood of you and everyone you know getting hit by lighting. Twice. On a single day.
像这样看：返回的数字probablePrime()不是质数的可能性低于您和您认识的每个人被照明击中的可能性。两次。一天之内。
Just don't worry about it.
别担心。
回答by Bart van Doormaal
You could also use the constructor of BigIntegerto generate a real prime:
您还可以使用的构造函数BigInteger来生成一个真正的素数：
BigInteger(int bitLength, int certainty, Random rnd)
The time to execute is proportional to the certainty, but on my Core i7 it isn't a problem.
执行时间与确定性成正比，但在我的 Core i7 上这不是问题。
回答by corsiKa
Make a method and wrap it.
制作一个方法并包装它。
BigInteger definitePrime(int bits, Random rnd) {
BigInteger prime = new BigInteger("4");
while(!isPrime(prime)) prime = BigInteger.probablePrime(bits,rnd);
return prime;
}
回答by Corona Luo
Random rnd = new SecureRandom();
System.out.println(BigInteger.probablePrime(bitLength, rnd));
The probability that a BigIntegerreturned by method probablePrime()is composite does not exceed 2^-100.
BigInteger方法返回的aprobablePrime()是复合的概率不超过 2^-100。
