title: Java BigInteger , number theory , modular arithmetic
body: <p>Anyone have an idea on how to implement such a problem in java ?</p>
  
  <p>"Implement a subroutine that takes three positive integer arguments (a; b; n) and returns the
  value of ( (a to the power of b) mod n), where the arguments are represented by about 100 decimal digits. Using four different methods."</p>
  
  <p>Thanks in advance</p>
  
  <p>UPD : Methods were be as following</p>
  
  <p>M1)</p>
  
  <pre><code>public BigInteger Result1(BigInteger a , BigInteger b , BigInteger n){
      BigInteger Res = new BigInteger("1");
      for (BigInteger i = new BigInteger("0"); !i.equals(b); i = i.add(new BigInteger("1"))) {
          Res = Res.multiply(a).mod(n);
      }
      return Res;
  }
  </code></pre>
  
  <p>M2)</p>
  
  <pre><code>public BigInteger Result2(BigInteger a , BigInteger b , BigInteger n){
      BigInteger Res = new BigInteger("1");
      for (BigInteger i = new BigInteger("0"); !i.equals(b); i = i.add(new BigInteger("1"))) {
          Res = Res.multiply(a);
      }
      return Res.mod(n);
  }
  </code></pre>
  
  <p>M3)</p>
  
  <pre><code>ublic BigInteger Result3(BigInteger a , BigInteger b , BigInteger n){
      if(b.equals(new BigInteger("0"))){
          return new BigInteger("1");
      }
      else if(b.mod(new BigInteger("2")).equals(new BigInteger("0"))){
          BigInteger Res = Result3(a,b.divide(new BigInteger("2")),n);
          return (Res.multiply(Res)).mod(n);
      }
      else{
          return ( (a.mod(n)).multiply(Result3(a, b.subtract(new BigInteger("1")), n)) ).mod(n);
      }
  }
  </code></pre>
  
  <p>M4)</p>
  
  <pre><code>public BigInteger Result4(BigInteger a , BigInteger b , BigInteger n){
      BigInteger Res = new BigInteger("1");
      while(!b.equals(new BigInteger("0"))) {
          if(!(b.mod(new BigInteger("2"))).equals(new BigInteger("0"))) {
              Res = Res.multiply(a).mod(n);
          }
          a = a.multiply(a).mod(n);
          b = b.divide(new BigInteger("2"));
      }
      return Res;
  }
  </code></pre>