title: BigIntegers to the power of BigIntegers
body: <p>I am trying to implement either the Fermat, Miller-Rabin, or AKS algorithm in Java using the BigInteger class.</p>
  
  <p>I think I have the <a href="http://en.wikipedia.org/wiki/Fermat_primality_test#Algorithm_and_running_time" rel="nofollow">Fermat test</a> implemented except that the BigInteger class doesn't allow taking BigIntegers to the power of BigIntegers (one can only take BigIntegers to the power of primitive ints). <strong>Is there a way around this?</strong></p>
  
  <p>The problematic line is denoted in my code:</p>
  
  <pre><code>public static boolean fermatPrimalityTest(BigInteger n)
  {
      BigInteger a;
      Random rand = new Random();
      int maxIterations = 100000;
  
      for (int i = 0; i &lt; maxIterations; i++) {
          a = new BigInteger(2048, rand);
  
          // PROBLEM WITH a.pow(n) BECAUSE n IS NOT A BigInteger
          boolean test = ((a.pow(n)).minus(BigInteger.ONE)).equals((BigInteger.ONE).mod(n));
  
          if (!test)
              return false;
      }
  
      return true;
  }
  </code></pre>