java - BigInteger.pow和BigInteger.isProbablePrime的复杂性是什么？

Java 7的 pow 类中的 isProbablePrime 和 BigInteger 方法的复杂性是什么？

我知道Rabin检验的简单实现方式复杂度为O(k(log(n())^ 3))，可以通过合并Schönhage-Strassen algorithm来实现长整数的快速乘法，从而降低复杂度。

最佳答案

假设使用标准算法，则复杂度为:

pow()             : O( M(n * exponent) )
IsProbablePrime() : O( M(n) * n )

在哪里:

n是操作数中的位数。

exponent是幂函数的指数。

M(n)是n x n数字乘法的运行时。我相信从Java 6开始就是O(n^2)。

pow()的解释:

对于长n位数字的输入操作数，加长到exp的幂，输出大约是n * exp位数字。这是通过二进制幂算法完成的，其中操作数在每次迭代时均平方。因此，复杂度变为:

O( M(n) + M(2*n) + M(4*n) + ... M(n * exp/2) ) = O( M(n * exp) )

这是一个几何总和，因此总和变为O( M(n * exp) )。

IsProbablePrime()的解释:

对于固定数量的Rabin-Miller迭代，每个迭代都具有O(n)位数大小的n x n乘法。因此，复杂度变为O( n * M(n) )。

关于java - BigInteger.pow和BigInteger.isProbablePrime的复杂性是什么？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7631772/