Pow and mod function optimization

I need to create an optimized function to count Math.pow(a,b) % c; in Javascript;

There's no problems while cou开发者_运维百科nting small numbers like:

Math.pow(2345,123) % 1234567;

But if you try to count:

Math.pow(2345678910, 123456789) % 1234567;

you'll get incorrect result because of Math.pow() function result that cannot count up "big" numbers;

My solution was:

function powMod(base, pow, mod){
    var i, result = 1;
    for ( i = 0; i < pow; i++){
        result *= base;
        result %= mod;
    }
return result;

Though it needs a lot of time to be counted;

Is it possible to optimized it somehow or find more rational way to count up Math.pow(a, b) % c; for "big" numbers? (I wrote "big" because they are not really bigIntegers);

Based on SICP.

function expmod( base, exp, mod ){
  if (exp == 0) return 1;
  if (exp % 2 == 0){
    return Math.pow( expmod( base, (exp / 2), mod), 2) % mod;
  }
  else {
    return (base * expmod( base, (exp - 1), mod)) % mod;
  }
}

This one should be quicker than first powering and then taking remainder, as it takes remainder every time you multiply, thus making actual numbers stay relatively small.

Your method is good so far, but you will want to do http://en.wikipedia.org/wiki/Exponentiation_by_squaring also known as http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method

The idea is that x^45 is the same as (expanded into binary) x^(32+8+4+1), which is the same as x^32 * x^8 * x^4 * x^1

And you first calculate x^1, then x^2 == (x^1)^2, then x^4 == (x^2)^2, then x^8 == (x^4)^2, then...

you can also use the mountgomery reduction in combination with exponentiation which is largely useful for large exponents > 256:

http://en.wikipedia.org/wiki/Montgomery_reduction#Modular_exponentiation

It has also been implemented in this BigInteger Library for RSA-encryption:

http://www-cs-students.stanford.edu/~tjw/jsbn/