Russian Peasant

'Russian Peasant' is a method for fast exponentiation. It is also known as 'exponentiation by squaring'. The basic idea is to exploit knowledge of the binary expansion of the exponent, by using selective repeated squaring. Depending on the factorization algorithm, and the size of the input number, this can lead to significant performance enhancement.

http://en.wikipedia.org/wiki/Exponentiation_by_squaring

Here is an on-line demo:
http://www.math.umbc.edu/~campbell/NumbThy/Class/BasicNumbThy.html#Modular-PowMod

The classic description is in Knuth (The Art of Computer Programming) 4.6.3
Java code as below:
 static BigInteger power(BigInteger x, BigInteger n, BigInteger mod) { 
// Knuth 4.6.3 - computes x^n modulo mod 
  BigInteger N = new BigInteger("0"); 
  BigInteger Y = new BigInteger("0"); 
  BigInteger Z = new BigInteger("0");
  N=n; 
  Y=one; 
  Z=x;
  while (true) { 
   if (N.remainder(two).compareTo(zero) > 0) { 
    N=N.divide(two); 
    Y=Z.multiply(Y).remainder(mod); 
    if (N.compareTo(zero) == 0) 
     return Y; 
   } 
   else { 
    N=N.divide(two); 
   } 
   Z=Z.multiply(Z).remainder(mod); 
  } 
 }