java - BigInteger.pow 和 BigInteger.isProbablePrime 的复杂度是多少？

Question

Java 7 方法的复杂性是什么pow和 isProbablePrime在BigInteger类(class)？

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

Answer 1

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

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

哪里:

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

pow() 的解释:

对于 n 位 long 的输入操作数的 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) )。