Java BigInteger nextProbablePrime方法是如何工作的？
Java BigInteger nextProbablePrime方法是如何工作的？
提问于 2019-06-24 23:09:57
我正在使用Java BigInteger类，并且对nextProbablePrime方法背后的算法很好奇。我知道一些有效的素性测试算法，比如Miller-Rabin，但不确定这里实现的是哪种算法。
尝试下面的代码，但仍然没有响应。
BigInteger number = BigInteger.ZERO;
number = number.setBit(82589933);
number = number.nextProbablePrime();回答 2
Stack Overflow用户
回答已采纳
发布于 2019-06-24 23:31:40
我已经通过了BigInteger的the source code。它在内部使用nextProbablePrime方法的 algorithm。
Stack Overflow用户
发布于 2019-06-25 02:55:54
为什么你的例子一次又一次地运行而不返回：
你的数字有8200万位长，而且(根据素数)这样的素数大约是8200万/ log_e(2)的数字。所以你要求Miller-Rabin测试大约1500万个候选者，其中每个候选者涉及8200万比特，并且每个检查都不是微不足道的。所以，是的，即使像Miller-Rabin这样的高效算法也需要一段时间来处理如此大得令人难以置信的输入。
(我记得有一次跑步将一个数字提升到另一个数字，花费了太长的时间，并向语言开发人员抱怨他们应该使用重复平方来更快地求幂……在我退后一步并意识到我的测试号也有数百万位数字之前。)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/56739468
复制相关文章
相似问题