Java BigInteger nextProbablePrime 方法如何工作？

Question

我正在使用 Java BigInteger Class 并对 nextProbablePrime 方法背后的算法感到好奇。我知道一些有效的素数测试算法，比如 Miller-Rabin，但不确定这里实现的是哪种算法。

尝试了下面的代码，但仍然没有反应。

BigInteger number = BigInteger.ZERO;
number = number.setBit(82589933);
number = number.nextProbablePrime();

Answer 1

我已经完成了 the source code of BigInteger. It is internally using the MillerRabin algorithm for the nextProbablePrime 方法。

Answer 2

为什么你的例子跑来跑去不返回：

你的数字是 8200 万位长，并且（按素数计算）这些素数大约相隔 8200 万 / log_e(2) 个数字。因此，您要求 Miller-Rabin 测试大约 1500 万名候选人，其中每个候选人涉及 8200 万位，并且每次检查都是 non-trivial。所以是的，即使像 Miller-Rabin 这样的高效算法也会在这样的 beyond-mind-bogglingly-big 输入上花费一段时间。

（我记得有一次运行将一个数增加到另一个数，花费的时间太长，并向 language-developer 抱怨他们应该使用重复的平方来更快地求幂......在我踏入之前返回并意识到我的 test-number 也有数百万个数字。）

Java BigInteger nextProbablePrime 方法如何工作？

How Java BigInteger nextProbablePrime method works?

java

biginteger