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

Question

什么是Java 7中的方法的复杂性pow，并isProbablePrime在BigInteger上课吗？

我知道 Rabin 测试的简单实现是 O(k(log(n))^3) 复杂度，并且可以通过结合Schönhage-Strassen 算法来快速乘以长整数来降低复杂度。

Answer 1

假设标准算法，复杂度为：

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

在哪里：

• n是操作数中的位数。
• exponent是幂函数的指数。
• M(n)是数字乘法的运行时间n x n。我相信是O(n^2)从 Java 6 开始的。

解释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) )。