title: What are complexities of BigInteger.pow and BigInteger.isProbablePrime?
body: <p>What are complexities of Java 7's methods <a href="http://download.oracle.com/javase/7/docs/api/java/math/BigInteger.html#pow%28int%29" rel="noreferrer"><code>pow</code></a> and <a href="http://download.oracle.com/javase/7/docs/api/java/math/BigInteger.html#isProbablePrime%28int%29" rel="noreferrer"><code>isProbablePrime</code></a> in the <a href="http://download.oracle.com/javase/7/docs/api/java/math/BigInteger.html" rel="noreferrer"><code>BigInteger</code></a> class?</p>
  
  <p>I know that simple implementation of Rabin's test is of O(k(log(n))^3) complexity and that can be reduced by incorporating the <a href="http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm" rel="noreferrer">Schönhage-Strassen algorithm</a> for the fast multiplication of long integers. </p>