What are complexities of BigInteger.pow and BigInteger.isProbablePrime?

What are complexities of Java 7's methods pow and isProbablePrime in the BigInteger class?

I know that simple implementation of Rabin's test is of 开发者_如何学JAVAO(k(log(n))^3) complexity and that can be reduced by incorporating the Schönhage-Strassen algorithm for the fast multiplication of long integers.

---

Assuming the standard algorithms, the complexities are:

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

where:

• n is the number of digits in the operand.
• exponent is the exponent of the power function.
• M(n) is the run-time for an n x n digit multiplication. Which I believe is O(n^2) as of Java 6.

Explanation for pow():

For an input operand of n-digits long raised to a power of exp, the output is roughly n * exp digits long. This is done by binary-powering algorithm where the operand is squared at each iteration. So the complexity becomes:

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

This is a geometric sum, so the sum becomes O( M(n * exp) ).

Explanation for IsProbablePrime():

For a fixed number of Rabin-Miller iterations, each iteration has O(n) multiplications of size n x n digits. Therefore, the complexity becomes O( n * M(n) ).

---

The short answer is that it isn't specified and therefore subject to implementor's choice.

---

If you want to have a look at the source, here it is: http://futureboy.us/temp/BigInteger.java.

Relevant material to your question here too: What complexity are operations on Java 7's BigInteger?