在BigInteger课程中,Java 7的方法pow和isProbablePrime有哪些复杂性？

我知道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×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迭代,每次迭代具有大小为n×n位的O(n)次乘法.因此,复杂度变为O(n * M(n)).