BigInteger#nextProbablePrime至少可以精确到64位数字吗?

我正在寻找使用BigInteger#nextProbablePrime生成质数的方法。此方法的文档指出以下内容:

  

此方法返回的数字为合成的概率不超过2 ^(-100)。

可以安全地假设此方法返回的每个值(在BigInteger.TWOBigInteger.valueOf(Long.MAX_VALUE)之间)都是素数吗?

lyz2046 回答:BigInteger#nextProbablePrime至少可以精确到64位数字吗?

从统计上讲,没有。已知有可能是错误的可能性。

实际上,是的。错误值的可能性极低。

,
  

此方法返回的数字为合成的概率不超过2 ^ -100

2和Long.MAX_VALUE之间有2 ^ 63位数。如果我们假设一个数字中的每个数字都是独立的,则可以得出一个数字错误的概率为(1-2 ^ -100),而所有这些数字都不正确的概率为(1-2 ^ 100)^(2 ^ 63),几乎是0。

换句话说,不是。

话虽这么说,但您必须很不幸才能真正找到这些数字之一。

使用一些更高级的数学进行编辑:

如果我们假设不是2和2 ^ 63之间的每个数字都是独立的,而是假设每个素数是独立的: 2^63/Log[2^63] (1 + 1.2762/Log[2^63]) = 2.17387*10^172之间有2^63个质数或更少。这样,您就有可能全部正确,如下所示:

N[Exp[Log[1 - 2^-100]*(2^63/Log[2^63] (1 + Rationalize[1.2762]/Log[2^63]))],1000] 
== 0.99999999999982851172...

(为了避免数值麻烦,我使用了日志的exp)。

,

This answer是正确的。我将进一步扩展它。

涉及的实际概率比文档中所述的要复杂得多,并且要小得多。但是文档中引用的概率通常是您想要的概率,因为这是最坏的情况。而提供更详细的答案将太数学化了。欢迎您来到see the analysis yourself

另一件事值得注意:正定长的完全确定性,100%正确的素数测试可用,比当前测试快得多。 BigInteger类的设计者显然得出结论,为此特殊情况编写代码不值得维护成本。我不同意,我打算提出一个错误/功能报告来建议这一点。

,

“安全”在这里是相对的。您需要对.probablePrime()的每个结果进行确定性测试,才能100%确定。 这种方法即使在64位数字上也无法100%准确地工作。

,

每当有可能发生或将不会发生某事的可能性时,那么肯定会发生不会。真正的问题是,您能应对事件发生的极端可能性吗?

,

其他答案正确地指出,虽然不能保证,但错误结果的可能性非常低。我想您可能会感兴趣的是:是否可以保证在您当前的BigInteger实现中

让我们想象一下,您正在Linux的Hotspot上使用OpenJDK 13.0.1,并且将长期使用它。假设您编写了一个测试,确认该特定版本的BigInteger返回的每个“可能素数”(最大2 ^ 31-1)确实是素数。测试花费了很多时间才能运行,但是没关系,您一生只需要运行一次,不是吗?

鉴于以上所述,您现在可以确定该特定版本的BigInteger是否可以保证在您下次运行时返回实际的素数吗?可能是这样,但是文档中没有保证BigInteger不使用某些随机化来在不同的会话中提供不同的结果。但是,您可以检查其源代码以确保这一点。

本文链接:https://www.f2er.com/3064323.html

大家都在问